I have the same problem here. Only on one remote host:
sylock@sylock-vmware:~$ ssh -vvv XX
OpenSSH_6.0p1 Debian-3ubuntu1, OpenSSL 1.0.1c 10 May 2012
debug1: Reading configuration data /home/sylock/.ssh/config
debug1: /home/sylock/.ssh/config line 1: Applying options for *
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: /etc/ssh/ssh_config line 19: Applying options for *
debug2: ssh_connect: needpriv 0
debug1: Connecting to XX[172.24.6.18] port 22.
debug1: Connection established.
debug1: identity file /home/sylock/.ssh/id_rsa type -1
debug1: identity file /home/sylock/.ssh/id_rsa-cert type -1
debug1: identity file /home/sylock/.ssh/id_dsa type -1
debug1: identity file /home/sylock/.ssh/id_dsa-cert type -1
debug1: identity file /home/sylock/.ssh/id_ecdsa type -1
debug1: identity file /home/sylock/.ssh/id_ecdsa-cert type -1
debug1: Remote protocol version 2.0, remote software version OpenSSH_5.1
debug1: match: OpenSSH_5.1 pat OpenSSH_5*
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_6.0p1 Debian-3ubuntu1
debug2: fd 3 setting O_NONBLOCK
debug3: load_hostkeys: loading entries for host fsmal989 from file
/home/sylock/.ssh/known_hosts
debug3: load_hostkeys: found key type RSA in file
/home/sylock/.ssh/known_hosts:269
debug3: load_hostkeys: loaded 1 keys
debug3: order_hostkeyalgs: prefer hostkeyalgs:
ssh-rsa-cert-...@openssh.com,ssh-rsa-cert-...@openssh.com,ssh-rsa
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug2: kex_parse_kexinit:
ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-group-exchange-sha256,diffie-hellman-group-exchange-sha1,diffie-hellman-group14-sha1,diffie-hellman-group1-sha1
debug2: kex_parse_kexinit:
ssh-rsa-cert-...@openssh.com,ssh-rsa-cert-...@openssh.com,ssh-rsa,ecdsa-sha2-nistp256-cert-...@openssh.com,ecdsa-sha2-nistp384-cert-...@openssh.com,ecdsa-sha2-nistp521-cert-...@openssh.com,ssh-dss-cert-...@openssh.com,ssh-dss-cert-...@openssh.com,ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,ssh-dss
debug2: kex_parse_kexinit:
aes128-ctr,aes192-ctr,aes256-ctr,arcfour256,arcfour128,aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,aes192-cbc,aes256-cbc,arcfour,rijndael-...@lysator.liu.se
debug2: kex_parse_kexinit:
aes128-ctr,aes192-ctr,aes256-ctr,arcfour256,arcfour128,aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,aes192-cbc,aes256-cbc,arcfour,rijndael-...@lysator.liu.se
debug2: kex_parse_kexinit:
hmac-md5,hmac-sha1,umac...@openssh.com,hmac-sha2-256,hmac-sha2-256-96,hmac-sha2-512,hmac-sha2-512-96,hmac-ripemd160,hmac-ripemd...@openssh.com,hmac-sha1-96,hmac-md5-96
debug2: kex_parse_kexinit:
hmac-md5,hmac-sha1,umac...@openssh.com,hmac-sha2-256,hmac-sha2-256-96,hmac-sha2-512,hmac-sha2-512-96,hmac-ripemd160,hmac-ripemd...@openssh.com,hmac-sha1-96,hmac-md5-96
debug2: kex_parse_kexinit: none,z...@openssh.com,zlib
debug2: kex_parse_kexinit: none,z...@openssh.com,zlib
debug2: kex_parse_kexinit:
debug2: kex_parse_kexinit:
debug2: kex_parse_kexinit: first_kex_follows 0
debug2: kex_parse_kexinit: reserved 0
debug2: kex_parse_kexinit:
diffie-hellman-group-exchange-sha256,diffie-hellman-group-exchange-sha1,diffie-hellman-group14-sha1,diffie-hellman-group1-sha1
debug2: kex_parse_kexinit: ssh-rsa,ssh-dss
debug2: kex_parse_kexinit:
aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,arcfour128,arcfour256,arcfour,aes192-cbc,aes256-cbc,rijndael-...@lysator.liu.se,aes128-ctr,aes192-ctr,aes256-ctr
debug2: kex_parse_kexinit:
aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,arcfour128,arcfour256,arcfour,aes192-cbc,aes256-cbc,rijndael-...@lysator.liu.se,aes128-ctr,aes192-ctr,aes256-ctr
debug2: kex_parse_kexinit:
hmac-md5,hmac-sha1,umac...@openssh.com,hmac-ripemd160,hmac-ripemd...@openssh.com,hmac-sha1-96,hmac-md5-96
debug2: kex_parse_kexinit:
hmac-md5,hmac-sha1,umac...@openssh.com,hmac-ripemd160,hmac-ripemd...@openssh.com,hmac-sha1-96,hmac-md5-96
debug2: kex_parse_kexinit: none,z...@openssh.com,zlib
debug2: kex_parse_kexinit: none,z...@openssh.com,zlib
debug2: kex_parse_kexinit:
debug2: kex_parse_kexinit:
debug2: kex_parse_kexinit: first_kex_follows 0
debug2: kex_parse_kexinit: reserved 0
debug2: mac_setup: found hmac-md5
debug1: kex: server-client aes128-ctr hmac-md5 none
debug2: mac_setup: found hmac-md5
debug1: kex: client-server aes128-ctr hmac-md5 none
debug1: SSH2_MSG_KEX_DH_GEX_REQUEST(102410248192) sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_GROUP
Write failed: Connection reset by peer
sylock@sylock-vmware:~$ ssh -V
OpenSSH_6.0p1 Debian-3ubuntu1, OpenSSL 1.0.1c 10 May 2012
sylock@sylock-vmware:~$ cat /etc/*release
DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=12.10
DISTRIB_CODENAME=quantal
DISTRIB_DESCRIPTION=Ubuntu 12.10
NAME=Ubuntu
VERSION=12.10, Quantal Quetzal
ID=ubuntu
ID_LIKE=debian
PRETTY_NAME=Ubuntu quantal (12.10)
VERSION_ID=12.10
sylock@sylock-vmware:~$ ldd /usr/bin/ssh
linux-vdso.so.1 = (0x711c)
libselinux.so.1 = /lib/x86_64-linux-gnu/libselinux.so.1