Então...
Se a impressão da chave ja está lá em "keys pending validation", você deve ter recebido um e-mail de confirmação. Você recebeu? Se sim, este e-mail deve ser decriptado para que possa ser lido seu conteúdo. Caso use o Thunderbird, instale nele a extensão "enigmail" que ela decripta a mensagem, se não, siga o 4º passo.