Sei que este é um post antigo, mas não vejo essa solução em outro lugar.
O problema não é o arquivo mlocate.db , como seria de esperar. São as permissões no executável mlocate . Isso consertará o problema:
sudo chmod 2755 /usr/bin/mlocate
Esta é a fonte do problema:
$ ls -lathr /usr/bin/mlocate -rwxr-xr-x 1 root mlocate 39K Nov 17 2014 /usr/bin/mlocate
Você precisa de um setuid no grupo para permitir que você execute o comando locate sem sudo . Depois de corrigido, sua saída ls deve ficar assim:
$ ls -lathr /usr/bin/mlocate -rwxr-sr-x 1 root mlocate 39K Nov 17 2014 /usr/bin/mlocate
Basta fazer um chmod , como outros recomendam em relação ao arquivo db , só funcionará até a próxima vez que alguém executar updatedb . Então as permissões serão redefinidas.