Como Alex apontou:
sudo apt-get clean
sudo apt-get install --reinstall $(dpkg --get-selections | grep -w 'install$' | cut -f 1)
O primeiro garante que o cache do apt esteja vazio. Dessa forma, o apt-get precisará baixar os pacotes dos repositórios. O segundo, primeiro você precisa de uma lista de todos os pacotes instalados, que é o que a parte $(...)
está fazendo, e então você está usando o apt-get para reinstalá-los. Existe outro jeito com o aptitude:
sudo aptitude --reinstall install '~i'
A pesquisa ~i
de "pacotes instalados".
Para ambos os métodos, você terminará sem nenhum pacote instalado automaticamente, portanto, você deve usar apt-mark showauto > packages
antes de fazer isso e sudo apt-mark auto $(cat packages)
para restabelecer a lista.