yeah looks like a dns issue , make sure that exchange it self is connecting to the global catalog/FSMO server ( your main domain controller ) ...

make sure the clients in your network are resolving the internal exchange server name , check your DNS records ...
or add it permanently to the hosts file under c:\WINDOWS\system32\drivers\etc