Ensure your DNS server doesn't point to an internet DNS service (eg: your ISP's DNS servers) in it's TCP/IP settings under Network Connections. It needs to point to itself.
Also according to this post the issue can be in NIC teaming (or drivers)
http://www.experts-exchange.com/OS/Microsoft_Operating_Systems/Server/Windows_2003_Active_Directory/Q_23255592.html