Descobri uma coisa. O problema está acontecendo apenas com estações Linux, por exemplo, Ubuntu 8.10 e Fedora 10. As estações Windows XP e Vista estão pigando normalmente entre si. Porém se dar um ping em qualquer estação (seja Windows ou Linux) na console shell de um Linux, não responde. O mesmo ocorrer se do Windows eu pingar um Linux. Porém os Windows se pingam normalmente e pingam nome de servidores de IP fixo...
Verificando no /etc/resolv.conf está o nameserver ip_do_meu_dns. Porém mesmo assim as estações Linux não conseguem resolver nome...
O que pode ser?