Unable to login to Exchange Server

We have Exchange Server 5.5 and Outlook 2000. One user (NT 4.0 wkstn) in his initial attempt to log in to the Exchange Server, gets the password box asking for: username, domain, and password. After supplying that, he is told that he needs to change his password after the initial login. But here is where he is unable to continue. He supplies a new password and Outlook returns the following error message:
Windows NT could not change your password. Please check the info and try again.
I’vedeleted his account and recreated it with no luck. I’ve changed his password numerous times also without luck.
Any ideas how to get this working? Thanks.
Jeff