Busca testdisk y photorec, ambos son libres y ambos hacen lo que pides (el segundo es específicamente para recuperar archivos y el primero es sólo una de sus opciones), leete su documentación y usa el que más se adapte a tus necesidades.
Ambos deberían estar en los repos de Ubuntu.
