If a host's operating system has been re-installed and had its public key regenerated sshing to it will of course fail because the new key doesn't match the old one.
Is there an easier way to tell ssh that you know that the host's key has changed and that you want it to be updated. I think it feels a bit error-prone to use a text editor or something like sed to remove the offending line.