It means they encrypted it to the wrong public key. Is the key ID that you omitted from the error message different from your key ID? I bet it is.