Definitivamente, tente photorec .
Apesar de seu nome soar como uma ferramenta de recuperação apenas para formatos de arquivo de imagem, ele é um gravador de arquivos extremamente poderoso e suporta muitos recursos tipos de arquivos diferentes (pelo menos frm e myi são suportados).
O Photorec faz parte do pacote testdisk no Ubuntu e em outras distribuições linux baseadas no Debian. Você pode instalá-lo facilmente com apt-get install testdisk como root.
Certifique-se também de experimentar a última versão do site da photorec, se a versão (provavelmente mais antiga) do Ubuntu / Repositórios Debian não dá resultados suficientes.