The Problem:
After some time the package database might get broken because you installed some incomplete stuff or did some installations manually, without thinking what you were doing. Now you get a warning everytime you run an apt-command, or even worse: it refuses to install anything.
How I fixed it:
run the following commands:
sudo bash
mv /var/lib/dpkg/status /var/lib/dpkg/status_bkup