El tema es que Windows debe estar resolviendo los nombres por netbios, por eso encuantra el servidor.
La solucion del archivo hosts es la que deberia funcionar.
Aviana, creo que entendiste mal. Tenes que modificar un archivo de la configuracion de los clientes Linux para que puedan accedes a tu servidor.
Postea el resultado del siguiente comando:
Como esta conformada la red? (Servidores, si hay servicios de directorio, etc)
Saludos.