In previous versions of Ubuntu (7.10), there was a problem with the SSH encryption key generator not creating a random key, but selecting one from a set of keys, leaving the machine open to brute-force attacks.
When upgrading to 8.04, the SSH keys are regenerated for the machine. When you try to connect to the recently updated machine, you will probably be rejected because the key no longer matches.
If you go to ~/.ssh/ on the machine that you're connecting from there is a “known_hosts” file. Deleting this file will force you to regenerate the local keys the next time you connect to the updated machine, solving your problems.
#cd ~/.ssh/ #rm known_hosts #touch known_hosts