I have been getting the same problem and ready to bang my head on the wall.
I followed the instructions as described above but still getting the same:
"the trust relationship between this computer and the primary domain failed"
Windows 7 pro x64 -> Win server 2003
Has anyone had any success in resolving this or some tips worth trying. I've tried looking through the 100's of forums with this issue but yet to find one that works.
Thanks in advance.