Check for Domain Name Service (DNS) errors in the event log.
If the Exchange server is a domain controller, make sure that the DNS is pointing back to the Exchange Server.
If the Exchange server is not a domain controller, verify that the DNS points to the correct DNS server.
To verify that the DNS settings point to the correct DNS server:
1. Open Network Connections.
2. Right-click the network connection you want to configure, and then click Properties.
3. On the General tab (for a local area connection) or the Networking tab (for all other connections), click Internet Protocol (TCP/IP), and then click Properties.