Ssh Error: Pty Allocation Request Failed on Channel 0

Suddenly I cannot access my server via ssh using my ssh-key. I can confirm that my ssh key is ok (tested with another server). For some reasons ssh asks user password, and even if I enter my password it says:

(~)$ ssh 
's password: 
PTY allocation request failed on channel 0

ssh stack on this error line until I press Ctrl+C.

The strange thing that I can pass command to execute via ssh, and it works:

(~)$ ssh  "uptime"
's password: 
 08:58:29 up 181 days,  6:12,  0 users,  load average: 0.00, 0.01, 0.05

I tried the same thing from two different independent computers, the problem is not on my ssh-client.

I was tried to reboot server but it does not help.

Server is Ubuntu 14.04.1 LTS.

What can I do to recover ssh access to server?