Este problema yo lo resuelvo de linux1 a linux2 de esta forma:
Se produce cuando cambias de ip las maquinas.
linux1:/home/usuario>ssh usuario@linux2
Error bla, bla,bla,bla
linux1:/home/usuario>cd .ssh
linux1:/home/usuario/.ssh>rm known_hosts
linux1:/home/usuario>ssh usuario@linux2
(conexion correcta).
Con el putty(cliente ssh grafico) me ha pasado lo mismo, y he borrado no se que archivo y a correr.
Espero haber servido de ayuda.
(es una solucion chapuzas, pero bueno)
Saludos y suerte.