O procedimento que você fala acima demora muito tempo mesmo ou você cancela logo, pergunto isso por que pelo que vejo ele está gerando os locales e isso demora um pouquinho mesmo, então você pode estar pensando ser erro e cancelando, aguarde um momento para ver se o processo terminar. Agora se demorar muito tempo mesmo e não sair da mensagem indicada é por que realmente o pacotes está com problemas.
Tudo que você baixar na internet dos repositórios do Ubuntu são colocados em /var/cache/apt/archives, portanto basta salvar os arquivos .deb presentes nesta pasta eu em um CD, por exemplo e depois que instalar novamente o Ubuntu copiá-los outra vez para a pasta /var/cache/apt/archives e aí ao tentar instalar algo dos repositório e quie seja da mesma versão do que já esta no cache ele não irá baixa já instalando o que está no cache, agora se já tiver novas versões nos repositórios vai ser ainda baixado.
Procure aqui no fórum sobre o AptonCD que é algo que visa automatizar isso de fazer backups de programas instalados dos repositórios.