Comment 3 for bug 543657

try this: https://answers.launchpad.net/ubuntu/+question/5435

It looks like the data on your drive got pwned, for whatever reason (check to see if you have /var/lib/dpkg). That link in answers.launchpad describes how to reinstall all the packages that are complaining, in order to recreate all the missing files(See the last couple posts). You may want to just skip that, backup your files, and reinstall entirely.