O seguinte resolve:
sudo gpg --keyserver hkp://keyserver.ubuntu.com:80 --recv-keys SOMEKEY
Se você vir algo assim:
W: GPG error: http://archive.canonical.com jaunty Release: The following signatures couldn't be verified because the public key is not available: NO_PUBKEY 40976EAF437D05B5
adicione a chave apropriada:
sudo apt-key adv --keyserver keyserver.ubuntu.com --recv-keys 40976EAF437D05B5
Você pode obter uma lista de repositórios aqui: link (mas não é recomendado adicionar atualizações x-org - pelo menos, certifique-se de fazer backup de você xorg.conf
)
Se você encontrar erros de repos anteriores - esvazie seu /etc/apt/sources.list.d
dir.