We had this problem too. Now Resolved. The easy way.
Firstly, an explaination of the situation:
I image the same PC many times in a week. To make it simple, I'l refer to only one of my (four) machines.
Now when I have an image on this machine, the
Computer Name is MFBOX2 as assigned by the DNS. It is connected to the domain as MFBOX2 in an OU.
I then downloaded another image onto that PC. The computer name was also called MFBOX2, again from the DNS.
I then removed that 2nd image from the domain, and renamed the computer to IMAGING-SCMS4.
I uploaded that image (for my backups) and downloaded the first image again.
This is where you'll run into the above problem.
Problem Explained:
Windows thinks it is still connected to the domain.
The domain no longer holds MFBOX2 anymore, as it was removed previously.
Windows says to the DC, "Hello, log this person in please."
The DC replies, "Who are you? Im sure you just left." and does not trust the windows machine anymore.
The issue is resolved if we reconnect the pcs to the domain.
Your right.
Windows then says, "Ok, whatever. Bye." and produces the error message.
By rejoining windows to the domain, the Domain Controller now recognises it again, and the trusted relationship is regained.
In short, what I believed happened with you, assuming you dont image, is that somehow the computer object was removed from the DC manually and not from the PC in question.
Sorry, I did try to make it technical, but analogies are more fun.