Originally Posted by rowan

Random thought: it could be something weird like an MTU path problem. That's where your end is sending (say) 1500 byte packets, but some intermediate link can only support (say) a maximum of 1488. There are protocols to automatically determine the maximum common MTU, but they're often rendered useless by aggressive firewalling. MTU path discovery issues can be tricky to diagnose because often the initial setup of a protocol (such as the TCP handshake) will succeed, but then everything just stalls once it starts streaming full sized packets.

Then again, if the transfer is succeeding eventually, it's probably not that...

Are you absolutely sure that your IP - the one you're connecting from - resolves on the destination FTP server?

Examples: (do this on the server)

$ host 8.8.8.8
8.8.8.8.in-addr.arpa domain name pointer google-public-dns-a.google.com.

$ host 1.2.3.4
Host 4.3.2.1.in-addr.arpa. not found: 3(NXDOMAIN)

Originally Posted by BigFurry

Is your client FileZilla?

You didn't say if you tried SSL FTP.
In the connection settings under Encryption there is
- Require explicit FTP over TLS
- Require implicit FTP over TLS
Worth trying both, it could change the communication a bit, and it might be a workaround.

Or better yet, use SFTP, which is really the best option if you have SSH access. Set SFTP in the FileZilla Protocol, and use your SSH credentials as user/pass.