That sounds like a local caching issue — an `apt-get update` first usually fixes that for me.

Or, you have a third-party APT repository specified in `/etc/apt/sources.list{,.d/*}` that you didn't install the keys for.

Or the NSA.