Anteriormente escribi sobre GetDataback un programa en windows de como recuperar archivos pero que pasa si usamos Ubuntu lo corremos con wine?¿ para este caso les traigo un aplicativo que me recomendaron lo probe y me saco de un apuro.
Esta probado en Ubuntu Lucid escribí en la terminal:

$ sudo aptitude install testdisk
Después
$ sudo photorec
Te pedirá que amplíes el terminal, esto es, usa pantalla completa.
Observaciones:
1. El programa no tiene garantía como todo free.
2. Ten cuidado.
3. Yo lo uso por lo menos en Jaunty y no he tenido problemas.
4. Encontrarás todo,todo, todo lo perdido.
5. Es una herramienta muy potente de informática forense.
6. Tendrás que crear una carpeta para depositar lo que recuperes.
7. No se lo cuentes a nadie porque es un secreto extraordinariamente bueno; yo colaboraría con sus inventores.