Is this an NT 4 Domain or an AD Domain?

Maybe try writing down or logging which Domain Controller is authenticating the user. Maybe it does not have the correct information or perhaps it can not contact a Global Catalog Server, or maybe your just running an OLD script due to replication issues.

See if there is some commonality of which Server authenticates the user.