Hi,
What version system(s) and VMPro are you using?
Are you using VMPro in IP Office mode or Intuity mode?
Are you using DS phones, DT phones, or SLTs?
Entering the password in handsfree mode or with the handset up?
I would suggest getting a password hash viewer - something that will view what's behind the **** in the password field in Manager. Just to see if they passwords are actually changing or whether it's VMPro just not recognising what the user is entering. I use
http://www.snadboy.com/RevelationV2.zip for this.
Have you tried accessing a remote user's mailbox from the local site? See if their password works from the local site.
Cheers