how to reproduce: create a file in your home named 'rh_bugs' in search files, Find files named: enter 'rh*' or 'rh_bugs', it wont' find it (Starting in folder is your home). Can't attach screenshot due to bugzilla error.
Well it's using "locate" not "find" so won't find files that were just created. It should probably do something like use "find" for your home dir and "locate" for system dirs, or something smart like that. http://bugzilla.gnome.org/show_bug.cgi?id=89535
Patch available on the upstream bug report.
Upstream bug closed, we will get a fix on next package version upgrade.
2.0.2-3 backports the fix
Fix confirmed with gnome-utils-2.0.2-4.