Common AWS EC2 mistake

Well, it's a common mistake for me...

You start a new instance in Amazon Web Services (AWS) Elastic Compute Cloud (EC2) using the ec2-run-instances command. You should include a keypair in the command line like this:
$ ec2-run-instances ami-2b5fba42 -k mykeypair

But if you forget to include the keypair an instance will still start up and appear in ec2-describe-instances. When you try to ssh into that node you get this error message:

$ ssh -i mykeypair root@ec2-75-101-234-79.compute-1.amazonaws.com
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@ 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
b0:b8:fa:f6:f2:c5:e8:2f:7b:9c:e8:44:b7:ff:a3:70.
Please contact your system administrator.
Add correct host key in /Users/jones/.ssh/known_hosts to get rid of this message.
Offending key in /Users/jones/.ssh/known_hosts:67
RSA host key for ec2-75-101-234-79.compute-1.amazonaws.com has changed and you have requested strict checking.
Host key verification failed.
lost connection

Confusing, until you realize your mistake...

You have to terminate that instance and then create a new one with a keypair.