This article is from the SSH - Secure Shell FAQ, by Thomas Koenig Thomas.Koenig@ciw.uni-karlsruhe.de with numerous contributions by others.
There are several possibilities why this could be the case; common
ones include
o The client host key is not stored in the known_hosts file. Note
that this has to be the canonical (usually, the fully qualified)
domain name.
o The client host does not have a reverse mapping in the name
servers. Note that ssh requires that it has both a reverse
mapping, and a forward mapping that contains the original IP
address.
o A multi-homed client or host does not have all of its IP addresses
listed in the DNS entry. Note that versions prior to 1.2.12 have
bugs in handling multi-homed hosts.
o User's home directory or ~/.rhosts is world or group-writable (see
StrictModes server configuration option).
o On some machines, if the home directory is on an NFS volume,
~/.rhosts and your home directory may need to be world-readable.
o The root account has to use ~/.rhosts or ~/.shosts;
/etc/shosts.equiv and /etc/hosts.equiv are disregarded for root.
o Confusion between RhostsRSAAuthentication and RSAAuthentication.
RhostsRSAAuthentication is a functional replacement for the 'r'
utilities; this requires the ssh program to be setuid root, a
secret key in /etc/host_key file on the client, a corresponding
public key entry in /etc/ssh_known_hosts, plus entries in
~/.[sr]hosts or /etc/[s]hosts.equiv.
RSAAuthentication is done on a per-user basis and requires a
~/.ssh/identity file on the client side (to be generated with ssh-
keygen), plus a matching ~/.ssh/authorized_keys on the server side.
 
Continue to: