Caro colega!

nos seus cliente linux deixe assim o resolv.conf

search <dominio1> <dominio2>
nameserver <ip1-do-dns>
nameserver <ip2-do-dns>

Explicações:
search - vai fazer uma busca nos seus dominios ou domínio (se for só um); aqui vc coloca o dominio que vc criou lá no dns;
nameserver - aqui vc coloca o ip do seu servidor dns
nameserver - se vc tiver mais de um server dns vc coloca o outro ip aqui;

Só isso.
Se o serviço dns tá configurado direitinho como vc disse, as maquinas vão conseguir pingar por nome.

QQC posta aqui.