Here are details of the machine I want to access using its hostname:

    $ hostname
    hostname
    $ cat /etc/hosts
    127.0.0.1	localhost
    127.0.1.1	hostname.company.local	hostname

It's a default Debian 6 (Squeeze) install, so I didn't fiddle with anything yet.

This is what I get from a machine trying to access above machine:

    $ ping hostname
    ping: unknown host hostname
    $ ping hostname.company.local
    ping: unknown host hostname.company.local