After upgrading from 5.0.15 NE to 5.0.16 NE, passwords will not change. I've tried from the web interface and cli:

su - zimbra
zmprov sp password

zmprov -d sp provides a wealth of information, but does not report any errors. Actuallly, come to think of it, the statement about upgrading could quite possibly be a red herring, as I do not know whether we had this problem before the upgrade...

zimbra.log says:
Jun 16 13:19:51 zldap2 slapd[7674]: syncrepl_message_to_op: rid 100 be_modify uid=adm,ou=people,dc=eecs,dc=wsu,dc=edu (0)

...any ideas where to look next?