Ubuntu – Access Windows machines from Ubuntu on local network by hostname

[I've searched a LOT for a solution to this issue, but if someone wants to point me to a related question and/or answer, please do!]

I have a local network over a broadband router with 3 Windows 7 computers and an Ubuntu VirtualBox VM on a Windows host. I can access the Windows computers from one another just fine, and I've configured Samba on Ubuntu so I can see and access the my-ubuntu computer from the Windows machines as well.

The problem is accessing Windows machines from Ubuntu by hostname. I can ping the Windows machines from Ubuntu by IP address, but I can't do a lookup by their names, win7-1, win7-2, win7-3.

I.e., smbclient -L 192.168.2.5 is successful, but smbclient -L win7-1 is not. smbtree sometimes shows the following, sometimes doesn't:

WORKGROUP
    \\MY-UBUNTU
    \\WIN7-1
    \\WIN7-2
    \\WIN7-3

• For the sake of debugging I've disabled all firewalls and enabled all read/write permissions everywhere (since they're all just my machines).
• I also know I can add entries to /etc/hosts for each individual machine, but I would like to learn how to get hostname lookup working dynamically

Question

How can I set up what I want to work? Ubuntu is running in a VirtualBox VM on a Windows host with Bridged networking set up, so I can't run a DNS server within Ubuntu (or can I?).

I think other newbies would also really appreciate a high-level overview, of where the DNS server should be, how the Ubuntu machine should use it, whether I need to change anything in the Windows machines' settings..I'm confused by all these packages and settings I've come across – resolv, libnss-mdns, avahi, dnsmasq, winbind..I just want to install and use what I need!