Cannot use apt-get/dpkg -- Input/output error

I have bumped into an issue that doesn't allow me to do anything related to apt-get: install, remove, etc. Whenever I try to do something (e.g. sudo apt-get install firefox -f) it gives me the same error message:

Reading database ... dpkg: unrecoverable fatal error, aborting:
 unable to open files list file for package `fontconfig-config': Input/output error
E: Sub-process /usr/bin/dpkg returned an error code (2)

I have tried to deal with the package fontconfig-config without success.

I have found that the "Input/output error" is usually linked with physical problems of the hard drive, but I do not think that's the case I am using that hd without any other problem.

I have tried removing the mention to the package in /var/lib/dpkg/status as mentioned here.

I have tried deleting all files related to the package in /var/lib/dpkg/info as I found somewhere.

But I still cannot do anything. The funny bit comes when I look for the file that is giving me troubles:

mecho@Ansible-MS-7680:/var/lib/dpkg/info$ ls fontconfig*
ls: cannot access fontconfig-config.list: Input/output error
fontconfig.list     fontconfig.postinst  fontconfig.preinst  fontconfig.triggers
fontconfig.md5sums  fontconfig.postrm    fontconfig.prerm

This is done after I deleted all files ... it looks like fontconfig-config.list still exists but it doesn't show up!

Any idea about how to solve the problem?

I am on kubuntu precise, fontconfig-config_2.8.0-3ubuntu9.1

I do not have smartmontools installed nor any other programme I could use to check the hard disk. The most similar think I seem to have is KDE Partition Manager but it doesn't allow me to check anything (the option appears unavailable). However, I think the problem is not the hd.

How do you suggests me to do the fs check? fcheck is not installed and I cannot think of any other command in bash (as I do not think I have anything else installed that could perform a check).

Thank you.

Edit: I have found the command (silly me), fsck. This is what I got:

/dev/sda1: recovering journal
Clearing orphaned inode 4456702 (uid=1000, gid=1000, mode=0140775, size=0)
Clearing orphaned inode 4456700 (uid=1000, gid=1000, mode=0140775, size=0)
Clearing orphaned inode 4456699 (uid=1000, gid=1000, mode=0140775, size=0)
Clearing orphaned inode 4456697 (uid=1000, gid=1000, mode=0140775, size=0)
Clearing orphaned inode 4456694 (uid=1000, gid=1000, mode=0140775, size=0)
Clearing orphaned inode 4456693 (uid=1000, gid=1000, mode=0140775, size=0)
Clearing orphaned inode 4456688 (uid=1000, gid=1000, mode=0140775, size=0)
Clearing orphaned inode 4456481 (uid=1000, gid=1000, mode=0140775, size=0)
Clearing orphaned inode 4456692 (uid=0, gid=0, mode=0100600, size=65536)
Clearing orphaned inode 4456689 (uid=1000, gid=1000, mode=0140775, size=0)
Clearing orphaned inode 4456709 (uid=1000, gid=1000, mode=0100600, size=714046)
Clearing orphaned inode 4456469 (uid=1000, gid=1000, mode=0140775, size=0)
Clearing orphaned inode 3672644 (uid=0, gid=0, mode=0100644, size=1595)
Clearing orphaned inode 1324021 (uid=0, gid=0, mode=0100640, size=1980)
Clearing orphaned inode 1324014 (uid=0, gid=0, mode=0100640, size=126)
Clearing orphaned inode 4456499 (uid=1000, gid=1000, mode=0100600, size=0)
Clearing orphaned inode 4456483 (uid=1000, gid=1000, mode=0100600, size=65536)
Setting free inodes count to 7147142 (was 7147702)
Setting free blocks count to 23891195 (was 23781617)
/dev/sda1: clean, 151930/7299072 files, 5292549/29183744 blocks

I'd start with checking your hard disk for errors. If you have smartmontools installed, run

sudo smartctl -d ata -a /dev/sda

if this is the disk on which you have Ubuntu installed and make sure that the value of Reallocated_Sector_Ct is 0. If it's non-zero - back up whatever you still can and replace the disk.

Otherwise if that (smartctl's output) checks out fine (hopefully), I'd follow up with a file system check.

I ran a second fsck -y (it found a lot of problems) and it eventually let me reinstall the problematic package.