It should be noted that there are other benign things that can cause this key change.
For example, most SSH clients builds a cache over hostnames and fingerprints. I get this problem a lot in my job as it involves a lot of machines on the same IP (but on different networks), thus my ssh client only stores the IP and fingerprint, and ignores the fact that it's on a different network, thus a different machine (hey, how could it know?). You would get the same warning if you've done a reinstall of the system (keys are normally generated during install), or if the hostname used to refer to a different machine that you've shelled into.
When the key has changed, and the machine is the same, you should think back if there's any reason for this change. Have you been tinkering with sshd lately? Some distros generate new keys if sshd is reinstalled/recompiled.
If none of the above is the case, then a possible scenario is that someone is doing a man-in-the-middle attack. Simply put, a machine that pretends to be your server, so that it can get your login-info when you try to log in. To pull this off, someone would have to either spoof your machines address/hostname, or control one of the data transit-points (routers, bridges, etc) between you and your machine.
If you get into the machine (either by appropriate commandline switches to your ssh client, or by removing the offening key from /home/username/.ssh/known_hosts), then my initial checks of intrusion detection would be:
- find /etc/ -mtime -3 (finds any files in /etc/ that changed during the past 3 days.. tweak the number to make sure it overlaps with whenever the issue started)
- check the appropriate logs in /var/log (secure, messages, etc)
- check if there are anyone else logged on to your system
- use the above listed find command to search for changes in your web-root that shouldn't be there (installing a backdoor in a php script is a common method of gaining unauthorized access)
If you have physical access to the machine, i'd get on its keyboard/monitor, and reboot into singleuser mode. This ensures that you and only you are on the system while doing these checks.
After confirming an intrusion, the first step is to clean out the system. As there's nothing important on it, the best approach is to do a complete reinstall, as it's very hard to clear out a system that has been under someone elses control for a significant period of time. (they've had plenty of times to install a lot of backdoors to make sure they keep their unauthorized access).
Second step is to track down how the system was compromised in the first place to ensure it doesn't happen again.