Problem changing password

We have several people who cannot change their password. They click on File, Security, User Security, enter their existing password, click Change Password, enter the existing password, enter a new password and click OK. They close Notes and re-open and they can’t login with the new password, they have to use the old password. Any suggestion?