locate usa um banco de dados gerado e atualizado pelo comando updatedb que é executado pelo cron (geralmente todas as noites). Portanto, é possível que seu banco de dados esteja desatualizado. Tente o seguinte e, em seguida, execute o comando locate novamente:
sudo updatedb