This is from the link provided by @Anonymous in the comments above. I have marked this answer as a community wiki.
Allowing Ubuntu to ping Windows NetBIOS names
Ubuntu is setup for Linux use, not Windows use, so we need to install a package that will allow Ubuntu to more readily mix in with Windows networks and use NetBIOS. This package is called "winbind".
Open a terminal and type in the following at the terminal prompt:
$ sudo apt-get install winbind
Once installed, we need to tell Ubuntu to use WINS (as provided by winbind) to resolve host names. Type in:
$ sudo gedit /etc/nsswitch.conf
... which will open the file into the Gnome Editor.
Scroll down to the line that starts with “hosts:”. In Ubuntu Jaunty, it looks similar to this:
hosts: files mdns4_minimal [NOTFOUND=return] dns mdns4
Add the word "wins" on the end of this line such that is now looks like:
hosts: files mdns4_minimal [NOTFOUND=return] dns mdns4 wins
Save and exit the editor.
Now let’s ping the name of our Windows box again.
$ ping alyx
... and it now resolves!
Pat yourself on the back.
Allowing Windows to ping Ubuntu NetBIOS names
This is just one half of the equation. We now need to allow Windows to be able to ping Ubuntu PCs using its NetBIOS name. This requires Ubuntu to recognise and respond to that request. We need to setup a server daemon to do this. In Ubuntu, this particular server daemon is called Samba.
Installing Samba is simplicity itself. Open a terminal and type in:
$ sudo apt-get install samba
Once that has finished, your Ubuntu PC will automagically respond to all NetBIOS queries for its hostname straight away, and that’s not just from Windows machines, but other Ubuntu machines (configured with the “winbind” package) as well.
Pat yourself on the back again.