O backup deve ser:
dpkg --get-selections > ~/Package.list
sudo cp /etc/apt/sources.list ~/sources.list
sudo apt-key exportall > ~/Repo.keys
e a restauração deve ser
sudo apt-key add ~/Repo.keys
sudo cp ~/sources.list /etc/apt/sources.list
sudo apt-get update
sudo apt-get install dselect
sudo dpkg --set-selections < ~/Package.list
sudo apt-get dselect-upgrade -y
... Se não estou enganado.