How to fix dpkg error [2]?

Every time I try to install or remove a package, I get this error. I thought maybe it was the hard disk, but a disk check gave me a clean bill of health.

dpkg: unrecoverable fatal error, aborting:
reading files list for package 'linux-headers-3.16.0-31': Input/output error
E: Sub-process /usr/bin/dpkg returned an error code (2)
A package failed to install.  Trying to recover:

I tried the solution of removing the listing for this file from the dpkg status file, but to no avail. I tried purging the package but no use. I'm stuck at this point as nothing I can find on Google helps.

Update:

This is now what the error says:

dpkg: unrecoverable fatal error, aborting:
E: Sub-process /usr/bin/dpkg returned an error code (2)
A package failed to install.  Trying to recover:

After trying: https://askubuntu.com/a/603305/1992

Update2:

Seems the drive has bad sectors, but the reallocated sector count is 0. The drive is relatively old, however, so I expect some issues. I won't be able to replace it immediately, and until then I would still like to be able to keep the system up to date (especially for security reasons).

I noted that there was an issue with coping some md5 checksums related to the package mentioned in the error, but I don't know what to do with those, such as if clearing them would allow dpkg to continue.

I found the answer here and here.

What puzzles me is that I tried this twice before and it didn't work. It probably worked this time because I used a script I found on launchpad answers that backed up and restored what it could... I don't know. Either way, here is the fix:

• pkexec gedit /var/lib/dpkg/status
• Search for the offending package by name and remove its entry.
• Save the file and exit gedit.
• run sudo dpkg --configure -a
• run sudo apt-get -f install just in case.
• Continue on if there are no errors.