I met this problem today morning after I started the sshd service. I think it is because I just updated my Fedora recently, and the ssh known_hosts file in your home directory should be updated too. There are 3 solutions to solve this,
http://www.cyberciti.biz/faq/warning-remote-host-identification-has-changed-error-and-solution/

The simple solutions to this problem are:
$ cd
$ rm .ssh/known_hosts
$ ssh ras.mydomain.com
or just:
ssh-keygen -R server.example.com