¿Como saber nombre de PC sabiendo su IP?

Prueba con nbtsat, no sé si viene preinstalado en ubuntu:

No se si te servirá pero con smbtree puedes ver los nombres de los equipos en red

y con nmblookup nombreequipo te da la ip.

Lo que pasa es que eso es para nombres NetBIOS, o sea Windows o equipos con Samba instalado.

Si es para nombres TCP/IP, pues buena pregunta, porque creo que no existe comando para pedir el nombre de esa misma manera, sino que hay que resolverlo por DNS. O compartir un fichero hosts con todos los equipos de la red, cosa harto incómoda en caso de tener que actualizarlo, salvo que se pueda (no lo he probado) usando un enlace a un fichero hosts en un recurso de red (NFS), de forma que sólo hay que actualizar ese fichero y les sirve a todos. Algo tipo:
ln -s /recurso_NFS/hosts /etc/hosts
Dicho recurso debe montarse automáticamente claro, lo pones en el fstab o con autofs.

Pues al final jugando con los comandos nmap y arp tengo mas o menos los datos que necesitaba.

Gracias a todos!!

Equipos windows tienes el nombre de NETBIOS, para equipos *NIX tienes que tener algún servicio de red en los equipos que te permita descubrirlos o bien un DNS.