We had the same issue, Do you have a mail cluster ?apparently policies only work if the user is connected his/her Home Mail server which can be found in the person document ( Mail Server field ) once this was corrected this started working for us, but this is a pain as we have 4 mail servers in our cluster. Here's a document i created for our helpdesk .. Hope this helps
When a Lotus Notes Client changes the password(Notes ID Password) it should sync the password with the IDVault and also generate a Adminp request to change the HTTP Password used for Sametime, iNotes Quickr and also Connections.
This synchronization is set by the Domino Client Policies for the Lotus Notes Client, If this does not happen do the following to make sure the settings are correct.
Go to Advanced>Connections make sure there is a connection document for the above “Home Mail server” if not create one
Go to Advanced>Locations>Online>Servers (Verify the mail server is correct)
Go to Advanced>Locations>Online> Open the document in edit mode by clicking the “EDIT” then go to Actions>Advanced>Set Update flag > Click “Yes” then Save & Close
*Note you will not see Advanced options when you go to Actions if you and not in edit mode
While you are in contacts press down CTRL+SHIFT and then go to View>Go TO scroll down to “$Policies view” chose the listed policies and delete them. this will update at restart if the settings are correct
Restart The Lotus Notes Client (password Sync will only happen when the client restarts)
Check the $Policies View to see if the deleted policies are back (they should be back if the procedure worked,if not set the update flag again and restart client)
Check with the Domino Admins to see if the AdminP request has come through to the server
**Adminp Request can be found in "all requests by action" > "Change HTTP Password in Domino Directory" under particular users name