Have you tried removing the client PC's from the domain and re-joining them to the domain?
It doesn't matter which PC I try on. However, I think I may have just fixed the problem. A backup Domain Controller was having replication issues. I fixed that, and now the user is able to log on. Not sure why that was the problem, as they should be able to log on with just one Domain Controller authenticating, but there ya go.
Thanks very much for the response.