Per default Ubuntu doesn't heed requests towards "computer names" like Windows does (\\COMPUTER and smb://COMPUTER). So you'll want to enable WINS (Windows Internet Name Service) host resolution. You need to install winbind with your package manager of choice, and modify /etc/nsswitch.conf slightly.
Code:
$ sudo aptitude install winbind
Pop up that nsswitch.conf in a text editor with superuser permissions and find the 'hosts:' line. Mine looked like this:
Code:
hosts:          files mdns4_minimal [NOTFOUND=return] dns mdns4
Now just add wins after files (order matters) and save the file.
Code:
hosts:          files wins mdns4_minimal [NOTFOUND=return] dns mdns4
Then restart samba for good measure. I think that ought to do it.
Code:
$ sudo service samba restart
On a sidenote, use smbtree to discover other computers in your network. Just hit enter when it asks for a password unless you need to authenticate towards the other computers to access their shares.
Code:
$ smbtree
Password: 
LAPPNET
	\\TLEILAX        		Linux Mint
		\\TLEILAX\Print_to_PDF   	Print to a PDF File
		\\TLEILAX\IPC$           	IPC Service (Linux Mint)
		\\TLEILAX\video          	
		\\TLEILAX\audio          	
		\\TLEILAX\downloads      	
		\\TLEILAX\print$         	Printer Drivers
	\\SUNSPIRE       		
		\\SUNSPIRE\video
		\\SUNSPIRE\downloads
		\\SUNSPIRE\pleiades
...