I found the solution in the first answer: https://answers.launchpad.net/ubuntu/+source/update-manager/+question/66668
Summarized, the following commands solve this problem:
sudo rm /var/lib/dpkg/status sudo cp /var/lib/ dpkg/status- old /var/lib/ dpkg/status sudo rm -rf /var/lib/ apt/lists/ * sudo dpkg --configure -a sudo aptitude update sudo aptitude upgrade sudo aptitude install -f