As Alex pointed out:
sudo apt-get clean
sudo apt-get install --reinstall $(dpkg --get-selections | grep -w 'install$' | cut -f 1)
The first one makes sure apt's cache is empty. That way apt-get will need to download the packages from the repositories. The second, first you need a list of all installed packages, which is what the `$(...)` part is doing, and then you are using apt-get to reinstall them. There's another way with aptitude:
sudo aptitude --reinstall install '~i'
The `~i` search for "installed packages".
For both methods you will end without any automatically installed packages, so you must use `apt-mark showauto > packages` before doing this, and `sudo apt-mark auto $(cat packages)` to reestablish the list.