I am offitially screwed. Last night I wanted to reinstall my laptop (which is also my only computer now), so I backuped the contents of my laptop's hard drive to an external usb hard drive as a 13 Gb tar.gz file and happily went on with a format and reinstall.
Of course, when I had completed the installation and went back to unpack files from the backup, I was greeted by a nice message from gunzip - "invalid compressed data--format violated".
Currently I am trying to follow gzip recovery guide that requires one to manually find the next undamaged compression block and make a new gzip file with standart header and then the undamaged compression blocks, but it is quite possible that data after that will also be damaged. Additionally I have no idea how tar will react to me giving it a middle of the archive, hopefully it will not get too confused. Unfortunately the damaged block is only 90 Mb into the 13 Gb file.
Oh, and of course there is a huge heap of really important files that I have no backup for that are on that backup. Fun, fun, fun.
Update: I have managed to recover two crucial OpenOffice.org documents from the formatted filesystem using Magic rescue and now I am proceeding with finding if I can recover anything from the .tar.gz backup file using Gzip recovery toolkit. It is buggy, but it is still better then doing it by hand.
Unfortunately, I also found out about some kind of hardware problem with my external harddrive - if I transfer lots of data to it (think a direct copy of a 13 Gb file), then it just locks up and stops responding until I power cycle it. If I turn off the USB2 support, then it works reliably, but very very slowly. This slows down my recovery attempts even more.