Celso,
Lembre-se da redução de menus que a janela do Nautilus tem sofrido. Com essas mudanças algumas opções passam a ser acessíveis clicando com o botão direito do mouse no ícone do Nautilus (quando aberto, é claro) no painel do Gnome ("bandeja" dos aplicativos abertos).
Lá você encontrará a opção "Connect to server" entre outras opções. Uma maneira que acho bem mais fácil, e que não senti esse problema por sempre usar dessa forma, é apertando Ctrl-L, o que é um atalho para "Enter Location" que é acessível da mesma forma que a opção que você deseja. Daí é só especificar o tipo de conexão desejada:
smb://
ftp://
sftp://
etc...
Abraços.