gpg: decryption failed: No secret key

[Joe Demeny]

I'm trying to decrypt a message using KMail and gpg and it fails. I then tried 
to manually decrypt the encrypted part and this is what I got:

$ gpg -v -d test
gpg: using character set `US-ASCII'
Warning: using insecure memory!
gpg: armor: BEGIN PGP MESSAGE
Version: GnuPG v2.0.9 (FreeBSD)
:pubkey enc packet: version 3, algo 16, keyid 72F9D3DCCF8503BE
        data: [2046 bits]
        data: [2048 bits]
gpg: armor header:
gpg: public key is CF8503BE
:encrypted data packet:
        length: unknown
gpg: encrypted with ELG key, ID CF8503BE
gpg: decryption failed: No secret key

I'm wondering what the error "No secret key" means? Am I trying to decrypt the 
message with the wrong key? Or have I broken my gpg setup?

-- 
Joe Demeny