As has been suggested above, it will most likely be a DNS problem. Below are some DNS pointers and tips to look for. Some will be obvious and some not.
1. Your DNS server should look at themselves for DNS i.e in their TCP\IP properties their own IP address should be listed in the DNS servers section. This goes for all DNS servers on your LAN. Alll domain controllers on a Windows 2000 - 2003 active directory network should have DNS running.
2. Forwarders. In the forwarders section of your servers DNS admin tool you should list your LEA's or ISP's external DNS servers. Do not list the other DNS servers on your network here.
3. Name servers. Ensure all of your domain controllers are listed here. If not add them manually.
4. Replication. Ensure that the replication options are set to replicate. As a failsafe measure allow your server to replicate to any other server requesting it.
5. DHCP settings. Ensure that you local DNS servers are set in your DHCP options. NOT your LEA's \ ISP's DNS servers.
6. Carry out the above steps on all of your domain controllers\DNS servers. I almost gurantee it will be one of the above things that is wrong.