Eu encontrei o problema.
Parece que locate é rápido porque depende de um banco de dados que ele cria para pesquisar coisas mais rapidamente. Este banco de dados é atualizado diariamente. O comando updatedb faz isso. Por acaso, updatedb é executado a cada 24 horas e 24 horas não passaram quando tentei pesquisar o arquivo usando locate , a partir do momento em que o arquivo foi criado. Depois de executar sudo updatedb , o locate conseguiu localizar o arquivo.
Sugiro ler as páginas de manual de locate e updatedb para obter mais informações.
Quanto a find , parece que eu estava impaciente e não esperei que terminasse a execução.