(o OP resolveu o problema e postou a resposta como comentário)
Aparentemente, a resposta é gastar horas em milhares de problemas só para descobrir que você está se bloqueando por meio de firewalls. Ainda parece estranho que os erros de DNS se propagassem do bloqueio do firewall, mas ai ... funcionou
Algo está tornando as chaves de recebimento do arquivo keyserver.ubuntu.com impossíveis e não sei ao certo por onde começar a tentar resolver isso.
Como exemplo, usaremos o aplicativo Spotify linux encontrado aqui: link
%pre%Para ficar claro, porém, isso não tem nada a ver com o Spotify. O mesmo resultado vem de cada uma das minhas tentativas de pegar as chaves do Ubuntu. Há algo errado do meu lado. Como sempre, qualquer ajuda para rastrear isso seria apreciada.
Antes de enviar isso, descobri que o problema está no meu DNS e / ou roteador. Atualmente eu tenho meu roteador configurado para usar o DNS do Google (8.8.8.8 / 8.8.4.4) e nos meus logs do roteador estou recebendo uma enxurrada de erros de DNS. O seguinte é um trecho:
%pre%Muito confuso. Eu nem tenho certeza se estou postando isso no site correto do StackExchange agora.