Ubuntu – SSH: hangs after “connection established”

I have an AWS EC2 instance to which I can't connect through one of Ubuntu servers. However, I can connect to the AWS instance through any machine(with and without private SSH key), but Ubuntu server cannot.

• Port 22 is opened on Ubuntu.
• AWS inbound rules configured regarding 22 port – no problems there.
• Regenerating SSH key didn't help too.

Telnet output:

$ sudo telnet xx.xx.xxx.xxx 22
Trying xx.xx.xxx.xxx...
Connected to xx.xx.xxx.xxx.
Escape character is '^]'.

SSH output (same output when private key is used):

$ ssh xxxxx@xxxxxxx -vvv
OpenSSH_5.9p1 Debian-5ubuntu1.4, OpenSSL 1.0.1 14 Mar 2012
debug2: ssh_connect: needpriv 0
debug1: Connecting to xxxxxx [xx.xx.xxx.xxx] port 22.
debug1: Connection established.
debug3: Incorrect RSA1 identifier
debug3: Could not load "meteor" as a RSA1 public key
debug1: identity file meteor type -1
debug1: identity file meteor-cert type -1

After it hangs. SSH doesn't give any timeout message and it can be stopped, by pressing ctrl+c . I guess after these lines, it must start SSH protocol.

Is it a networking problem or SSH client problem?