I open up a nautilus window and select "Connect to Server..." from the file menu. I enter in the name of my host, choose "SSH" for the protocol, and fill in the user name. After clicking "Connect" I see my host mounted on the Desktop, but if I try to open it I get a dialog that says 'Opening "<remotehostname>". You can stop this operation by clicking cancel." After waiting a few minutes I click cancel. My remote host never shows up. If I right click on the host icon on the desktop and select "Properties" I get a message which says "Creating Properties window. You can stop this operation by clicking cancel." Unmounting the server gets rid of the desktop icon, so at least that part works. I can successfully mount secure WebDAV shares and SMB shares, but ssh servers always choke. I have tried it with and without DSA keys installed and with and without the remote host in my known_hosts file. The effect is the same. I'm using nautilus-2.16.0-7.fc6 on an FC6 system which was upgraded from FC5.
I ran rm -rf .nautilus killall nautilus and that fixed it.