Eu acho que você precisa instalar o programa de localização. Em um sistema debian lenny, o arquivo / usr / bin / updatedb é um link simbólico para / etc / alternatives / updatedb, que é um link simbólico para /usr/bin/updatedb.findutils.
Usando o dpkg -S, você pode descobrir a qual pacote um arquivo pertence:
$ dpkg -S /usr/bin/updatedb.findutils
locate: /usr/bin/updatedb.findutils
Então, eu acho que você precisa instalar o locate e executar o updatedb como root.
Edit: sim, você precisa do pacote locate. No arquivo /usr/share/doc/findutils/NEWS.Debian.gz você pode ler:
locate is no longer included in the findutils package. It has been split off to a separate package "locate".
e depois em /usr/share/doc/findutils/changelog.Debian.gz, no changelog em 11 de novembro de 2007:
Split off locate/updatedb to a separate package.