When the mentioned problem is faced, check whether there is any comminication issues between Exchange Server and DC.
It could be because of,
1> Firewalls in between incase Exchange and DC are in seperate subnet
2> Check whether tcpip,sys file of Exchange and DC is of minimum version as per KB913446.
3> Check whether DCs have any issues.