Para solucionar esto, encontré este post en ubuntuforums, que si bien es viejo, me solucionó el problema en Hardy.
Primero hay que editar /etc/nsswitch.conf:
sudo vi /etc/nsswitch.conf
En la línea que dice:
hosts: files mdns4_minimal [NOTFOUND=return] dns mdns4
Tenemos que agregar wins, por ejemplo en este caso:
hosts: files mdns4_minimal [NOTFOUND=return] dns mdns4 wins
Luego, hay que instalar el paquete winbind:
sudo apt-get install winbind
Y listo, con eso ya podemos reconocer las máquinas windows por su hostname.