I've got several Ubuntu machines on my network at home, but the DNS is provided by a windows server (2K). When I ssh to them from another , if I ssh to them as "machine" I can't connect, but if I connect as "machine.local" I can connect.
I think similarly, I can't connect from a windows client (like putty).
What's going on here? - it's clearly an Ubuntu thing.
By default, Ubuntu includes Avahi. This is an implementation of zeroconf which allows computer hostnames to be resolved with the virtual ".local" name. Whenever your computer tries to connect to "hostname.local", Avahi will perform local network broadcasts to see if there any computers with that hostname. Other computers running Avahi (or something compatible) should answer.
If you look in /etc/nsswitch.conf, you will find the following line:
hosts: files mdns4_minimal [NOTFOUND=return] dns mdns4
The mdns4_minimal (mDNS client) is the configuration setting that makes this redirection work.
Your question actually suggests that avahi is running successfully as you say that you can connect to your Ubuntu computers using "hostname.local". However, you do not make it clear ("When I ssh to them from another, ...") if you are trying to connect from another Ubuntu computer, or from another Windows computer. Without installing other software such as Bonjour, Windows computers cannot resolve zeroconf-style "hostname.local" names.
To fix your issue, you just need Avahi. This announces your Ubuntu machine names to the Windows lot.
sudo apt-get install avahi-daemon
machinename.local works thanks to another implementation of zeroconf (of which Avahi is also) called Bonjour, created (IIRC) by Apple. It's installed by default. I don't know why Avahi isn't also but given the confusion it causes people, it probably aught to be.
There's more on this on Wikipedia: http://en.wikipedia.org/wiki/.local
