Why ssh client breaks connection in expecting SSH2_MSG_NEWKEYS state?

[Yuri]

I have a client host that I don't have access to now, which attempts to 
establish ssh connection back to my BSD server using the private key.
Client runs this command:
/usr/bin/ssh -i ~/.ssh/my_key_rsa -o "ExitOnForwardFailure yes" -p 
$HPORT $HUSER@$HOST -R $LPORT:localhost:$LPORT -N

On the server debug log looks like this:
Connection from NNN.NNN.NNN.NNN port 43567
debug1: HPN Disabled: 0, HPN Buffer Size: 65536
debug1: Client protocol version 2.0; client software version 
OpenSSH_5.9p1 Debian-5ubuntu1
debug1: match: OpenSSH_5.9p1 Debian-5ubuntu1 pat OpenSSH_5*
debug1: Remote is not HPN-aware
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_6.2_hpn13v11 FreeBSD-20130515
debug1: permanently_set_uid: 22/22 [preauth]
debug1: list_hostkey_types: ssh-rsa,ssh-dss,ecdsa-sha2-nistp256 [preauth]
debug1: SSH2_MSG_KEXINIT sent [preauth]
debug1: SSH2_MSG_KEXINIT received [preauth]
debug1: kex: client->server aes128-ctr hmac-md5 none [preauth]
debug1: kex: server->client aes128-ctr hmac-md5 none [preauth]
debug1: expecting SSH2_MSG_KEX_ECDH_INIT [preauth]
debug1: SSH2_MSG_NEWKEYS sent [preauth]
debug1: expecting SSH2_MSG_NEWKEYS [preauth]
Connection closed by NNN.NNN.NNN.NNN [preauth]

Client breaks connection right after 'expecting SSH2_MSG_NEWKEYS'.

I can always successfully connect to this server myself, and successful 
log continuation looks like this:
debug1: SSH2_MSG_NEWKEYS received
debug1: KEX done
debug1: userauth-request for user minsk service ssh-connection method none
debug1: attempt 0 failures 0
...

When I have set this client up, it was able to connect to similar BSD 
server system over the local net. So it does have the correct key. But 
over the internet connection now fails like this.

What can possibly cause client to break connection after 'expecting 
SSH2_MSG_NEWKEYS', and not proceed to SSH2_MSG_NEWKEYS?

I tried the same with similar linux client system running in VM, and it 
succeeds to connect. I also tried to downgrade server from version 6.2 
to 5.8, and both versions exhibit the same problem.

Yuri