Talvez você realmente esteja procedendo algo errado, mas vale te avisar que a pesquisa do nautilus é bem ruim, e é comum que falhe em encontrar arquivos que realmente existem.
Se você necessita de uma ferramenta de pesquisa mais precisa eu te recomendaria que procurasse neste fórum e no google por estes dois programas:
-beagle
e
-tracker