Do you have a forward lookup zone for your Active Directory domain name?
(From ADU&C)
If not, create one. And set it to allow dynamic updates.
Does your AD Domain name match you Primary DNS suffix in your ipconfig /all?
If not see:
257623 Domain Controller's Domain Name System Suffix Does Not Match Domain
Name
http://support.microsoft.com/?id=257623&sd=RMVP also see here, it's for both 2000 and 2003:
http://www.ehow.com/how_2002003_fix-active-directory-dns-problems.html