Há muito muito tempo atrás TestDisk e PhotoRec fizeram milagres pra mim,
não tenho como lembrar agora o seu modo de uso, mas lembro de ter sido
relativamente simples mesmo considerando que à época eu tinha um
entendimento bem limitado de bash e gnu em geral.
E como o Listeiro bem apontou, usando o "dd" vc pode criar uma imagem do
disco e trabalhar em cima dela. Com isso vc evita a perda de dados
(considerando que os inodes foram liberados para o sistema).
Esse site dá um bom panorama, se inglês não for um óbice:
http://www.makeuseof.com/tag/recover-deleted-files-from-your-linux-system/
--
-- André Nunes Batista