OK, first what version of Fedora are you running? This probably shouldn't matter too much, but good to know. Second, what type of system / environment are you trying to connect to? Is it a true Windows server (ie Windows 2003, Windows 2008, etc.)? Is it an Active Directory environment or are you just using a basic Windows Workgroup?
I typically use KDE / Dolphin, not Gnome / Nautilus, so I'm not sure about your Nautilus issue. I just tested on my Fedora workstation with Nautilus and there is a Browse Network option which seems to work, but it probably depends on what type of server / environment you are connecting to. You could try mounting it at the command line. Something like...
Code:
mount -t cifs -o user=<your user name>,workgroup=<your workgroup/domain name> //<server name>/<share name> /mnt/<share name>