Win2k woes

I have a client that is running a windows 2000 server in mixed mode with win NT clients:

“My NT4 clients can join the domain, but upon rebooting receive an error message that their computer account is either missing or the password on that account is incorrect.”

This has been submitted to Microsoft and is on hold until Thursday, anyone have any ideas?