AMIs that have the same ssh host key pairs as other public amis will be made private by amazon to prevent man-in-the-middle attacks, so always remove SSH Host Key Pairs (they will be regenerated with new unique keys automatically)

rm /etc/ssh/ssh_host_dsa_key
rm /etc/ssh/ssh_host_dsa_key.pub
rm /etc/ssh/ssh_host_key
rm /etc/ssh/ssh_host_key.pub
rm /etc/ssh/ssh_host_rsa_key
rm /etc/ssh/ssh_host_rsa_key.pub