Eu tive o mesmo problema e levei algum tempo para corrigi-lo, sem formatar:)
Basta seguir esta dica:
e2fsck: Get a newer version of e2fsck!
Você precisa baixar a última versão do e2fsck, compilá-la e usar esta versão.
Aqui estão alguns passos a seguir (use 1.43.1 ou mais recente):
wget http://downloads.sourceforge.net/project/e2fsprogs/e2fsprogs/v1.43.1/e2fsprogs-1.43.1.tar.gz
tar xzf e2fsprogs-1.43.1.tar.gz
cd e2fsprogs-1.43.1
./configure # <== if this step fail, check the config.log file, it could just be that you are missing the "libc6-dev" package on your system
make
cd e2fsck/
./e2fsck
Voila!