Ubuntu – Can I ping via IP address but not hostname

I have a media/file server running Ubuntu 10.10 Maverick Meerkat, connected via cable directly to a DSL router, which also acts as a network switch.

The router uses DHCP to dynamically assign IP addresses. I'd like to keep it as such, if possible. I have friends come in and it's easier for them to connect.

From my desktop (Ubuntu 10.04 Lucid Lynx) I connect via wireless to the router. I can ping the media server and ssh into it using it's IP, but it fails when I use the hostname.

When I ping and ssh wirelessly from my Netbook (Crunchbang Linux), it strangely enough works using the media server's hostname.

That said, I believe it may not be a router configuration issue, but something on my desktop I have to configure.

I tried turning off the firewall, on both sides (sudo ufw enable/disable).

What else can I check or try? Thanks 🙂