Originally Posted by acid_kewpie
delete the relevant line in the known_hosts file and you'll get it automatically added next time.
That'll fix it, but there could be something more serious here.
OP: Did you recently reinstall that machine or make a major upgrade? If not, I'd wonder why it has a new host key.