Unable to install any updates through update manager/apt-get upgrade

I have fixed the problem with these instructions.

So the solution is the following:

1. Go into the /var/lib/dpkg directory
2. Make a backup of the status file
3. Edit the status file
4. Search the package that gave the error

5. Just delete the lines from this package (but let all other lines that concern other packages even if they contains the broken package in their "Replaces" or "Depends" fields)

   […]

6. Save changes in the status file

7. Run: sudo dpkg --configure -a

8. Force the re-installation of missing dependencies (because now, there are some):

   sudo apt-get -f install
   

   I think that if the broken package does not depend on any other package (could be rare), just reinstall it:

   sudo apt-get install the_package
   

9. Everything is fine now can update, upgrade, or install new packages!

It should be noted that I had a few differences to the solution given there. The status file was not easy to edit (as it is an important file and never meant to be edited). Any edits made there should be done with care, and the file should be backed up before you make any changes.

I had to repeat steps 4-8 three times (each time the error would be the same just with a different package). Finally when all the packages were removed, I was able to reinstall them, and it fixed my problem.

It can happen that the disk is corrupted with inodes.

With a live CD, run this command

sudo fdisk -l

note the disk and partition, it could be /dev/dsb1 then repair it:

sudo fsck -y /dev/sdb1

Reboot, and return on the system

sudo apt-get -f install
sudo apt-get update
sudo apt-get upgrade