the windows netowkringprotocal is a discusting protocal in genaral, The whole lets elect someone to be the browsemaster etc. etc...
You might like to try checking if your linux boxes know who the browsemaster is (my guess is they don't have a clue who they are, hence why they can't see anyone yet everyone can see them)
nmblookup -M WORKGROUP
(where workgroup is your workgroup)
this should tell you if they can see the browse master..
in all honesty i wouldn't bother browsing shares, I would just mount them.
mount -t smbfs //192.168.0.1/sharename /mnt/mountpoint
where 192.168.0.1 is the ip of the computer you wish to mount and sharname is the name of the share
smbclient -L 192.168.0.1
will list all the shares on a host..
it seems the simplist solution, unless you have time to run through your /etc/smb.conf and make certain everything is setup right...