Here are the bug reports that seems to be causing all the fuss in Ubuntu: https://bugs.launchpad.net/ubuntu/+source/nautilus/+bug/209520
https://bugs.launchpad.net/ubuntu/+source/gvfs/+bug/207072
It appears that the gvfs package is what is causing all of the problems.
The exact problem we were having was that under Gnome, browsing the network (Places->Network->Windows Network) we could see the shares, but trying to access them would either lock up the Nautilus window (had to be force quit and to see the computers again we had to restart samba) or it would just display an empty folder. Mounting the share manually on the command line worked. Using KDE worked. Opening Nautilus, File->Open Location->smb://server/share worked! Just we could not browse through Nautilus.
This particular problem has been around since the Hardy alpha release so there are plenty of bugs and forums posts.
At least to me, it sounds like what you have posted is similar to the problems we had/Ubuntu Hardy has. Are you using gvfs? Does this sound like your problem to you? Or am I just way off? :-P
Good luck and have fun!
~S~