Corri o mesmo problema ao usar as mesmas instruções. No meu caso eu estava seguindo diretamente a documentação da comunidade usando uma versão LTS do Precise Pangolin e acabei baixando a versão mais atualizada da fonte do ubuntu-keyring. Percebi ao copiar as chaves que criei foram 2011.11.21.1.
Eu movi de volta uma versão usando
apt-get source ubuntu-keyring=2011.11.21
Depois disso tudo pareceu funcionar mais perto do descrito. Este post me apontou na direção certa.