Apt-get reports NO_PUBKEY gpg error for keys that are present in trusted.gpg

Ubuntu 14.04
apt 1.0.1ubuntu2.1

'apt-get update' has started showing several warnings like the following, even though the keys are present:

W: GPG error: http://extras.ubuntu.com trusty Release: The following signatures couldn't be verified because the public key is not available: NO_PUBKEY 16126D3A3E5C1192
W: GPG error: http://archive.canonical.com trusty Release: The following signatures couldn't be verified because the public key is not available: NO_PUBKEY 40976EAF437D05B5 NO_PUBKEY 3B4FE6ACC0B21F32
W: GPG error: http://qgis.org trusty InRelease: The following signatures couldn't be verified because the public key is not available: NO_PUBKEY 030561BEDD45F6C3
W: GPG error: http://dl.google.com stable Release: The following signatures couldn't be verified because the public key is not available: NO_PUBKEY A040830F7FAC5991
W: GPG error: http://dl.google.com stable Release: The following signatures couldn't be verified because the public key is not available: NO_PUBKEY A040830F7FAC5991
W: GPG error: http://archive.ubuntu.com trusty Release: The following signatures couldn't be verified because the public key is not available: NO_PUBKEY 40976EAF437D05B5 NO_PUBKEY 3B4FE6ACC0B21F32
W: GPG error: http://archive.ubuntu.com trusty-updates Release: The following signatures couldn't be verified because the public key is not available: NO_PUBKEY 40976EAF437D05B5 NO_PUBKEY 3B4FE6ACC0B21F32
W: GPG error: http://archive.ubuntu.com trusty-security Release: The following signatures couldn't be verified because the public key is not available: NO_PUBKEY 40976EAF437D05B5 NO_PUBKEY 3B4FE6ACC0B21F32

sudo apt-key clean didn't help

The only ultimate solution was to remove all the keys from /etc/apt/trusted.gpg.d and run

sudo apt-key adv --keyserver keyserver.ubuntu.com --recv-keys KEY

for each key that was missing.

Here is a reference bug for 13.10
https://bugs.launchpad.net/ubuntu/+source/apt/+bug/1263540