Also check hostname resolution on the client machine (can it resolve machinename.domain to an ip-address). You can check by pinging machinename.domain
Code:
wim@btd-techweb01:~$ ping btd-techweb01
PING btd-techweb01.mca.naspers.dom (172.31.212.190) 56(84) bytes of data.
64 bytes from btd-techweb01.mca.naspers.dom (172.31.212.190): icmp_seq=1 ttl=64 time=0.040 ms
64 bytes from btd-techweb01.mca.naspers.dom (172.31.212.190): icmp_seq=2 ttl=64 time=0.030 ms
...
...
When you ping by name, it should show you the ip-address as marked in bold. If not, the hostname is not resolved.