I know you had tried, I just wasnt sure if you tried as the Enterprise Admin as opposed to just a Domain Admin. As far as rejoining to the domain are the users trying it themselves or are you trying it with a Domain Admin account?

I found this article in regards to your most current error:
http://www.derkeiler.com/Newsgroups/...5-08/0134.html