testdisk
está bem disponível em reposições vívidas: testdisk (6.14-3build2) [universe]
Basta ativar o repositório do universo:
sudo add-apt-repository "deb http://archive.ubuntu.com/ubuntu $(lsb_release -sc) universe"
sudo apt-get update
sudo apt-get install testdisk