Then the signatures don't match, or the fingerprint is wrong. If you're relying on long-term data access, messages encrypted against or signed by the true key don't match. This is an area in which PGP and SSH differ markedly. PGP is used to encrypt and authenticate data which tends to persist, SSH data used only in session. While both can use long-lived keypairs, it's the PGP keys you're more likely to notice changing (though SSH cclients tend to report this happening).
Yes, that means verifying your keys, and probably through an out-of-band method.
