I don't have an answer for you just yet, but I have some suggestions to get there.
First, rather than focus on the model of the phone in question, you should validate that you are indeed working on a 5000 phone system.
Then, you are going to want to troubleshoot this yourself without involving the user. That way, you'll be able to get the answer faster. In other words, since you can reset the password, dial in as that user to see if you can access the voice mail system.
Then, you want to identify the voice mail system you are using. Is it Enterprise, Basic or some other product?
Hope this helps you narrow down the issue. Good luck.