Try to lookup your server's hostname at a client and your client machine's hostname at a server. If one of two takes long to lookup then you should change that hostname or add it to the /etc/hosts.
To know hostname of the server type
hostname in the command line. Then on another server type
nslookup <hostname>. If you get the IP address in the command's output — hostname resolves correctly. Example:
$ nslookup google.com
If hostname cound not be resolved you'll get answer like this:
$ nslookup google.local
** server can't find google.local: NXDOMAIN