DNS clients can find machines by either IP address or by host name, but the server can only find machines by their IP addresses.
Probable cause and solution:
When using DNS you must include dns in the hosts record of every machine's nsswitch.conf file. For example:
hosts: dns nisplus [NOTFOUND=return] files
hosts: nisplus dns [NOTFOUND=return] files