They can't have encrypted the message to your PGP public key. Tell them to resend it the message actually encrypted with your public key. It's a common mistake, but a recoverable one.@Wadozo, it's not possible for the sender's PGP key to be the issue if the recipient is unable to decrypt a message, since the sender's PGP key was never involved in encrypting any data unless they mistakenly encrypted the message to their own public key. To PGP Club! Investigate the Russian Postal System analogy I posted in the thread to see why. It would be like locking a box and sending it to your friend with no key attached. Then your friend gets it and thinks: "WTF, I have no key for this!".While we're here, why are you using keyservers? That is not really a good idea for us here. You shouldn't upload anything to a server from your GPG software unless it's torified (downloading non-SRian information is fine). It's a hypothetical, but it could be used as an exploit to deanonymize you. Better safe than sorry!