I see, probably what is happening is that they are expecting you to use the old SSH version 1 approach for launching the SFTP server on the remote side.
Just to test that this is the case, what happens if you run these commands...?
plink *remoteHost* -p *remotePort* -v sftp-server
plink *remoteHost* -p *remotePort* -v /usr/lib/sftp-server
Does anyone of them hangs (that means that the sftp-server is listening) instead of exiting with an error?
Once you find how to launch the remote sftp-server, tell Net::SFTP::Foreign to use the same command with the open2_cmd constructor option. For instance:
my $sftp = Net::SFTP::Foreign->new(open2_cmd => "plink $host -p $port
$sftp->error and die "SFTP connection failed: " . $sftp->error;
update: and BTW, I think the root of the problem is an incomplete chroot'ed configuration for sshd in the remote side. Probably, they have not configured sshd to use internal-sftp server for the SFTP subsystem.
Ask them to check that the sshd_config file contains the following line:
Subsystem sftp internal-sftp
(a how-to: http://www.debian-administration.org/articles/590