Messenger 5.1 log in problem

we're running Windows Messenger 5.1 through our Exchange 2000 server. One of
my users is unable to log into messenger and gets the error message that the
username or password is not correct for his address.
I've disabled/re-enabled IM for his account, verified all of the addresses
and uninstalled/reinstalled the client.
He shows up when another user searches for new contacts so I know the
account does exist.
Exchange recognizes the underlying account because he is able to access his
mailbox.
I believe that it is probably an Exchange issue, any suggestions on where to
start looking?

Bill