Comment 23 for bug 356022

Mlaverdiere,

Yes, you do need to have the "samba" package installed because it contains nmbd, the netbios P2P name lookup daemon. Otherwise, your system tries only DNS for the name lookups, which fail for the aforementioned reason.

I've become more experienced with Linux, and my recommended complete workaround to this issue is as follows:
1. Install the "samba" package.
2. Edit the line for "hosts" in /etc/nsswitch.conf so that "wins" is inserted right after "files".
e.g., if your nsswitch.conf has this "hosts" line:
hosts: files mdns4_minimal [NOTFOUND=return] dns mdns4 wins
change it to:
hosts: files wins mdns4_minimal [NOTFOUND=return] dns mdns4
Do this even if "wins" was not on the original line, still add it after "files". As a standard precaution, you should backup your original /etc/nsswitch.conf also.

What this does basically, is it makes linux to both lookup hostnames via netbios (wins) in general, and prioritize those name lookups over DNS name lookups. This mimics the default behavior of Windows.
(Step 2 may not be necessary for many users like Mlaverdiere because the samba suite uses its own name resolve order by default (the "name resolve order" line in smb.conf.), rather than the global /etc/nsswitch.conf file for all Linux programs.)

Also, some newer home wireless routers both:
A. Tell DHCP clients (your computers) to use it as the DNS server. E.g., it will tell them to use 192.168.1.1.
B. Automatically create DNS records for those DHCP clients.
This feature resolves the issue completely, and making my workaround unnecessary.