Execute um liveCD ou USB e monte sua partição com o sistema de arquivos como "readonly", supondo que sua partição Ubuntu esteja em sda2, você pode executar este comando
mkdir ~/recovery/
sudo mount -o ro /dev/sda2 ~/recovery/
E agora o comando de recuperação apenas para um arquivo:
sudo extundelete /dev/sda2 --restore-file /home/username/Videos/movies/movie.avi
Para recuperar um diretório:
sudo extundelete /dev/sda2 --restore-directory /home/username/Videos/movies/
Ou restaure tudo:
sudo extundelete /dev/sda2 --restore-all
Isso deve funcionar. Eu