Using his credentials at this 'other' machine, do you get his inbox succesfully?
What happens if this user goes to another pc and tries it?
Have you observed either in person or remotely viewed his desktop while he trys to login?
He might be simply fat fingering it.
He might be forgetting to use the Domain\ preceeding his NTID.
He may in fact not know his NTID especially if your XP security policies allow cached last login names to be displayed.
If you were to logon to a different user profile on the same pc as the user is experiencing the issue and then tried to open OWA and used the users credentials, does it work then?
If so then it's likely the users profile in windows is in someway corrupted, I see this not often, but regularly enough to know to troubleshoot it in this way.
If so I rename the profile, and let windows re-create the profile when they log in next, then move their documents and psts but no cookies or ntuser.dat etc files to the new profile.
I hope some of these suggestions will help you determine the problem.
If you need more help be sure to provide the feedback of what you've ruled out so far.
Rev