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

I have been running Ubuntu 12.04 for the past few weeks. I recently tried to download and install some files through the Update Manager. It located a few files, downloaded them, but then failed to install them. It gave the error:

installArchives() failed: (Reading database ... 
(Reading database ... 80%
dpkg: unrecoverable fatal error, aborting:
 reading files list for package 'libasn1-8-heimdal': Input/output error

I tried using apt-get upgrade but a similar error was produced:

Reading package lists... Done
Building dependency tree       
Reading state information... Done
The following packages will be upgraded:
  icedtea-6-jre-cacao icedtea-6-jre-jamvm openjdk-6-jre openjdk-6-jre-headless
  openjdk-6-jre-lib
5 upgraded, 0 newly installed, 0 to remove and 0 not upgraded.
Need to get 0 B/34.6 MB of archives.
After this operation, 1,024 B of additional disk space will be used.
Do you want to continue [Y/n]? y
(Reading database ... 80%
dpkg: unrecoverable fatal error, aborting:
 reading files list for package 'libasn1-8-heimdal': Input/output error
E: Sub-process /usr/bin/dpkg returned an error code (2)

Any help would be greatly appreciated. Thanks in advance.

Edit: Here's some extra information that may be useful. My original problem was that the Ubuntu Software Centre would not open. I found that the Update Manager and Synaptic Package Manager also failed to open. They all gave an error along the lines of:

"installArchives() failed: dpkg: error: reading package info file '/var/lib/dpkg/available': Input/output errorError in function:"

After much googling I seemed to fix that problem as the package managers would open again. When I then tried to download and install any updates from the Update Manager I got the error at the beginning of this post.

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