Connect to sftp times out while ssh works fine in terminal

I have a server at my ssh office and two client computers. One of the clients is in the same LAN as the server. It can connect fine using gvfs (nautilus) from Ubuntu 11.10. The other client is a remote one, it connects via the internet and it gives this error:
Error: Timed out when logging in
Please select another viewer and try again.

Weird thing is that connecting using a terminal with the ssh command works just fine. Also, other ssh servers can be used with gvfs on that machine without problems.

ProblemType: Bug
DistroRelease: Ubuntu 11.10
Package: gvfs 1.10.0-0ubuntu1
ProcVersionSignature: Ubuntu 3.0.0-12.20-generic 3.0.4
Uname: Linux 3.0.0-12-generic x86_64
NonfreeKernelModules: nvidia
ApportVersion: 1.23-0ubuntu3
Architecture: amd64
Date: Thu Oct 27 22:17:57 2011
InstallationMedia: Ubuntu 11.10 "Oneiric Ocelot" - Release amd64 (20111011)
ProcEnviron:
 LANGUAGE=en_US:en
 PATH=(custom, no user)
 LANG=en_US.UTF-8
 SHELL=/bin/bash
SourcePackage: gvfs
UpgradeStatus: No upgrade log present (probably fresh install)