New developments:
It appears that some of these user's passwords expired. XP only notifies you once that your password will expire in 14 days and then never again. If the password expires, the user is denied access using the cached credentials. This is a suspicion and I will try to test that next week.
Also, under article 175468, there is a fix for the computer account that we have sent to several users to try. This may not be the solution given the issue with the password issue. Again, we are testing it to see if it works or not. If not, we will have a flood of remote users that cannot log on at all.