Você tem duas opções, das quais você pode fazer uma ou ambas:
-
Instale o Samba (apt-get install samba) e ative o componente nmbd. Isso fará com que o servidor Ubuntu atenda solicitações de nome NetBIOS de clientes Windows sem mais configurações.
-
Adicione um registro ao seu servidor DNS. Você mencionou que o servidor DNS é RedHat EL 4, então provavelmente estará executando o ISC Bind. A configuração está em
/etc/named
e os manuais compatíveis com RedHat ainda estão disponíveis aqui: link
Editar: O segundo destes é preferível, você não deve confiar no NetBIOS para fazer a resolução de nomes para você.