ssh fails with "Warning: Remote Host Identification Has Changed!"

Answer

Example:
# ssh myuser@cupcake
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!     @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
IT IS POSSIBLE THAT SOMEONE IS DOING SOMETHING NASTY!
Someone could be eavesdropping on you right now (man-in-the-middle attack)!
It is also possible that the RSA host key has just been changed.
The fingerprint for the RSA key sent by the remote host is
d7:3b:a3:5b:88:d2:f4:96:80:0d:8e:a0:8d:44:a2:d2.
Please contact your system administrator.
Add correct host key in /home/myuser/.ssh/known_hosts to get rid of this message.
Offending key in /home/myuser/.ssh/known_hosts:4
RSA host key for cupcake has changed and you have requested strict checking.
Host key verification failed.


If you are confident that the host key changed for a known reason (i.e. a re-install of the openssh filesets on the server), then you can use the ssh-keygen command, as the user who received the error, to remove the offending key.

# ssh-keygen -R cupcake
/home/myuser/.ssh/known_hosts updated.
Original contents retained as /home/myuser/.ssh/known_hosts.old

Alternately, you can run the ssh-keygen as root, but you will need to specify the known_hosts file reported in the error.

# ssh-keygen -R cupcake -f /home/myuser/.ssh/known_hosts
/home/myuser/.ssh/known_hosts updated.
Original contents retained as /home/myuser/.ssh/known_hosts.old


Then try the ssh again. You will be prompted to confirm that you trust the new host key.

# ssh myuser@cupcake
The authenticity of host 'cupcake (127.0.0.1)' can't be established.
RSA key fingerprint is d7:3b:a3:5b:88:d2:f4:96:80:0d:8e:a0:8d:44:a2:d2.
Are you sure you want to continue connecting (yes/no)?


After you type 'yes', ssh will add the new key to your known_hosts file and proceed.

Warning: Permanently added 'cupcake' (RSA) to the list of known hosts.
Last unsuccessful login: Mon Dec  6 13:51:17 CST 2010 on /dev/lft0
Last login: Wed Feb 16 07:00:03 CST 2011 on ssh from icecream.austin.ibm.com
**************************************************************
*                                                            *
*                                                            *
*  Welcome to AIX Version 6.1!                               *
*                                                            *
*                                                            *
**************************************************************
$