Right. Here's the situation.
My Fedora 12 laptop has samba installed, and samba's domain is set to match the one used by the rest of the network, so the Windows computers can connect, and be connected to.
This is using the same as the Ubuntu Karmic desktop PC sat beside me, which can do this perfectly, as well as access network shares of other connected Linux computers.

My laptop cannot see or access any other computer on the network, neither of the two Windows (One XP, one 7) ones, nor the two Ubuntu ones (One Jaunty, one Karmic).
Of all of them, only the Ubuntu Karmic can see and access a single shared folder on my laptop, which is the ~/Public folder, shared via Samba. It can write to and from it.

No other computer can see this share, nor my laptop, and my laptop cannot see any computer at all.

can you see the shares by IP?? i had the problem with mine where i could browse via IP but not by name. in the end it was down to the nmb service not running on the server

I have no idea how to make sharing work by IP address, until now, all computers simply appeared in Nautilus' Network tab. It's only Fedora that can't do this, using the same samba settings as the Ubuntu Karmic one.