Você deve ser capaz de restaurá-lo com o testdisk. Testdisk está nos repositórios do Ubuntu, instale-o com o software center ou o apt-get
sudo apt-get install testdisk
Testdisk é um utilitário de linha de comando, há um guia passo-a-passo (com fotos) aqui