O Launchpad-Getkeys (um pequeno script compactado em um .deb para facilitar a instalação) importa automaticamente todas as chaves GPG ausentes.
Para instalar e usar, abra um terminal e copie / cole os seguintes comandos:
cd ~/Downloads
wget https://launchpad.net/~nilarimogard/+archive/webupd8/+files/launchpad-getkeys_0.3.1-1%7Ewebupd8%7Emaverick3_all.deb
sudo dpkg -i launchpad-getkeys*.deb
sudo launchpad-getkeys
O primeiro comando acima muda o diretório para sua pasta Downloads, o segundo faz o download do .deb, o terceiro comando instala o .deb e o último comando executa o script "launchpad-getkeys" que importa automaticamente todas as chaves GPG ausentes.
Se você estiver usando um proxy, algumas coisas precisam ser alteradas, por isso me avise se precisar de informações sobre isso também.
A propósito, vejo que você tem alguns outros erros também, não apenas chaves GPG. Parece que você tem alguns arquivos .list PPA quebrados (por exemplo, vejo um erro 404 não encontrado para o PUP WebUpd8 que não pode ser desde que o PPA existe desde o Jaunty até o Natty - talvez sua conexão com a Internet esteja inativa ?).