con updatedb (da root) aggiorni il database dei file presenti e poi con locate in un attimo fai la ricerca.
Per saperne di più man updatedb e man locate.

Od altrimenti credo che anche ubuntu abbia qualche utility grafica di ricerca (qualcosa come il "kfind" di kde, ma dato che ubuntu usa gnome non so ....).