Have you ever noticed those odd folders under Active Directory DNS such as:

_msdcs
_sites
_tcp
_udp

Those are important -- don't delete them!

I was in the process of migrating an older, and failing, Windows 2003 domain controller to a secondary Windows 2003 domain controller when I encountered a problem.  After a brief search, I discovered the folders I mentioned above were missing from the replacement server's DNS.

I ran the following commands:

dcdiag /fix
netdiag/fix
ipconfig /flushdns
ipconfig /registerdns

At this point you can restart the server or you can launch services and restart the Server service.  Be certain after it restarts that the following services have also restarted:

Net Logon
Distributed File System
Computer Browser

As a parting comment, I should mention that I have not attempted this sequence on a more recent DNS server.  In fact, I've only encountered this problem a few times and in all instances they were 2003 servers.