Hi i'm having this same problem when trying to connect to one of my sftp locations, using Ubuntu 9.10 (up to date) and doing "Places->Connect to server"
The server which is giving me the problem is running Solaris 9 and the following version of SSH:
OpenSSH_3.1p1, SSH protocols 1.5/2.0, OpenSSL 0x0090603f
I regularly use the same method to connect to other sftp location without problems.
I tried connecting to the sftp location in question from the command line and recived the following error:
Connecting to <server>
subsystem request failed on channel 0
Couldn't read packet: Connection reset by peer
Connecting to the same server with FileZilla using sftp, works just fine.