Acontece que o build do Ubuntu tem alguns problemas. Construir a partir da fonte ajuda:
apt-get remove extundelete
apt-get install build-essentials e2fslibs-dev
tar -xjf extundelete-VERSION.tar.bz2
cd extundelete
./configure
make
src/extundelete --restore-all image.raw