Getting "Host key verification failed" error message when you try to ssh to any server including localhost

In case any of you ever get the "Host key verification failed" error message when you try to ssh to any server including localhost. Thanks kaisen.

Symptoms:
Unable to ssh to any server including localhost when using a non-root account.
Consistently getting the "Host key verification failed" error message even when

~/known_hosts is already empty or doesn't exist
~/known_hosts never gets updated with new host keys

Reason:
Device pointed to by /dev/tty is not of 666 permission.

Resolution:
chmod 666 /dev/tty

Example:
Failed ssh attempts to localhost and other servers:

root@myserver:/etc/ssh>su - account1
myserver% ssh devusr@localhost
Host key verification failed.

myserver% ssh devusr@myserver
Host key verification failed.

root@myserver:/etc/ssh>su - myname
-bash-3.00$ ssh -x myname@myserver
Host key verification failed.

-bash-3.00$ ssh -x myname@myserver
Host key verification failed.

The culprit:
root@myserver:/etc/ssh>ls -l /dev/tty
lrwxrwxrwx 1 root other 26 Sep 11 2006 /dev/tty -> ../devices/pseudo/sy@0:tty

root@myserver:/etc/ssh>ls -l /devices/pseudo/sy@0:tty
crw--w---- 1 root tty 22, 0 Dec 15 20:20 /devices/pseudo/sy@0:tty
chmod 666 /dev/tty:

root@myserver:/etc/ssh>chmod 666 /devices/pseudo/sy@0:tty
root@myserver:/etc/ssh>ls -l /devices/pseudo/sy@0:tty
crw-rw-rw- 1 root tty 22, 0 Dec 15 20:20 /devices/pseudo/sy@0:tty

root@myserver:/etc/ssh>su - account2
-bash-3.00$ ls -l /devices/pseudo/sy@0:tty
crw-rw-rw- 1 root tty 22, 0 Dec 15 20:20 /devices/pseudo/sy@0:tty

ssh should now works and you are able to add new host keys to ~/known_hosts:

-bash-3.00$ ssh -x myname@myserver
The authenticity of host 'myserver (10.100.10.100)' can't be established.
RSA key fingerprint is 43:27:c1:aa:b9:c9:f1:21:33:11:aa:dd:ee:ff:10:9f.
Are you sure you want to continue connecting (yes/no)? yes
Warning: Permanently added 'myserver,10.100.10.100' (RSA) to the list of known hosts.

Password:
Last login: Mon Dec 15 19:20:41 2008 from myserver2
Sun Microsystems Inc. SunOS 5.9 Generic May 2002
$ Connection to myserver closed.
-bash-3.00$ logout