You can also try photorec. I've used it in the past and have had great success with it. You may have to install it from apt-get or synaptic though.
Fortunately, you're given the option of what types of files you wish to recover and for the most part, it really does a good job. The only negative complaint I have about it is that it takes again as much space as the files you're trying to recover and stores the recovered files in several smaller folders -without- their original names. So, let's say for instance, you're recovering all your .gif files, you'll have to look at each file separately, to identify it. Then of course, you can cut 'n' paste to where ever you wish to keep 'em.
Another 'negative' as I can see it, is that it also uses as much space for recovery as the original files sizes, so if you're hurting for available HD space, it's gonna be a bit dicey at best. But with that said, I've successfully recovered my .avi files, .gif, .jpg, .png, text documents, etc. However, if you've reformatted your HD, you may still be out of luck.
Another option is in using Parted Magic and is bootable from a CD rom or USB stick. It too, has a data recovery mode but I've not used it so far. However, if that works like everything else included on the disk, it can be a life saver for recovering files from a trashed OS. I'm currently in a situation where I had a Linux upgrade fail and thanks to some spare HD space on other HD's, I've been able to recover and transfer all my critical files to them, so I'm left with a completely clean HD to work with. When he new OS is set up and operating correctly, I'll just transfer my stuff back to it.
PartMagic will work for several different OS's and I think everyone who owns a computer should have a copy of it, since it's a free program. Just take the time to explore it fully once you have a copy so that you'll know what it's capable of doing for you. It really is, in my opinion, an outstanding compilation of software.
Good luck with your recovery.