This is usually due to skeleton DNS records left in the domain directory for domain controllers that no longer exist or function. Make sure that the only DCs in msdcs and the other sub-domains of the AD DNS do not have references to non-existent domain controllers and taht they are all set to the correct, current IP addresses.