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.