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 files
hosts: nisplus dns files