Sounds like a corrupt DNS database. Have you tried to delete the DNS record on the server? You probably need to delete the records in Forward and Reverse (if you have one) lookup zone. Remove the computer record on the AD and try again. May be a good idea to restart the server (if possible) before trying.
I once had the same problem with a XP machine and that solved the problem. Good luck.