Ter o mesmo problema levou-me a outro post sobre forçar o apt-get a adquirir uma conexão IPv4 que resolveu meu problema. Eu citei a resposta do outro fórum por conveniência.
% bl0ck_qu0te%Fonte: link
Eu tenho um 12.04 LTS VPS que não parece mais ser capaz de apt-get de nada. Ele se conecta ok para patches de segurança, mas ao instalar qualquer coisa, simplesmente fica travado em 0% tentando se conectar a us.archive.ubuntu.com . Eu tentei pingar us.archive.ubuntu.com e está funcionando. Alguém sabe como resolver isto?
Atualizando isso para futuros leitores, descobri que poderia consertá-lo trocando para v4 por v6 usando /etc/gai.conf.