1. Try changing the "netbios" name in your Samba config to your actual hostname (I presume your Linux PC is *not* named "samba").
2. I can't imagine that it's still necessary ... but Samba (like Win9x shares before it) *required* that you have the same username with the same password on both the client and the server.
Please try creating such a user (on both the Linux and Windows sides), and make sure he owns at least one "test share" you publish from Samba.
3. On Windows, I can access my Samba share like this:
[Start], run,
\\myhost\myshare (where "\\myhost" is the name of my PC, and "\myshare" is the share)
4. On Linux (Suse 9.x), I usually access Windows shares using the "Konqueror" web browser:
smb:/mywindowshost/mywindowsshare
Here's more info that might help:
http://www.faqs.org/docs/Linux-HOWTO/SMB-HOWTO.html