This problem is somewhat common on OpenVZ.
The problem can be fixed by chmod 000 /sbin/start_udev or by commenting out the /sbin/start_udev line in /etc/rc.sysinit

The problem is udev doesn't set up /dev with pty properly, which cripples ssh.