All those errors point to a faulty DNS setup. Verify DNS is installed, integrated with AD, and functioning correctly. Your DC's Event Viewer shold have a DNS section (or whichever machine is managing the DNS). Check it for errors.
Where is the DNS Server relative to the client? Same subnet or different subnet? Can your client "see" the DNS Server?
Can you provide any details about the network topology?
Edited by JebediahTBone, 26 December 2007 - 12:53 AM.