Ok, here's another thing you may quickly check on the domain server.
Is it possible you "renamed" this person's username on the domain? If so, it can get confusing at times. Display Name, full name, actual logon name may be different, and it is the logon name you should use to logon.
If you think this could have happened, in the Domain Server, open
Active Directory Users and Computers from the Adminisstrative Tools.
Locate the malfuncioning user. Properties. Open the "Account" tab.
Check there what the "logon name" is, as well what the pre-windows 2000 logon name is (if you have it in there). One of those two should be used to logon, and not the full name or the display name or whatever name this user object has in the AD.

Edit:
To explain what I mean here and how confusing this may get, my user account could be

- "Taym" as a <object name> in the AD, and this is what it is shown when you look at the list of users of a specific organizational unit in the Active Directory USers and Computers applet.
when you get into the properties of such AD object (user), though:
- "John" in the <first name> field, "Smith" in the <last name> field, but
- "J. A. Smith" in the <display name> field
** - "john.smith" in the <logon name> field
** - "JOHNS" in the <pre-windows 2000 logon name> field

Only those with the ** would work to log you on the domain.

In rare complex organizational setups, this is actually very versatile. But, it can get a mess also.