Amazon EC2 - remote host identification has changed

You may get the following message when you ssh into your EC2 machine:

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    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 a host key has just been changed.
The fingerprint for the RSA key sent by the remote host is
aa:c3:4d:d2:db:64:17:f0:b3:9c:77:d7:47:2f:31:ab.
Please contact your system administrator.

This can happen when you are associating your Elastic IP to another instance.

All you need to do is to remove the known_hosts file

rm ~/.ssh/known_hosts