GPG decryption error, "No secret key"

[eggrock]

I'm encrypting a file and sending it our to a customer that uses GPG and they're getting a "No secret key" error when they try to decrypt the file. It also gives them our key ID. That makes sense since we're using the encrypt-to-self option; the file is encrypted with both their key and our key. This is routine except for the decryption failure.

The recipient confirms that the key we're using to encrypt with has a corresponding private key on their keyring, but something is incompatible.

We're using McAfee E-Biz server 8.1.1 -- Unknown what flavor of GPG they're using but it's a DH/DSS key using CAST5. Their key looks kosher from what I can tell.

I don't see anything on Google that looks useful. Any ideas?