Either you're copy and pasting it incorrectly or the person who sent you the message didn't send it to your public key correctly, ask the person to resend it.