Could you be more specific? Are you using Windows XP?
1) Use a partial file name, not the whole file name.
2) Make sure you clicked “All files and folders”.
3) Try restarting your computer.
This is probably not the best way, but installing a third-party search utility, such as Google Desktop, can provide faster (indexed) search that might not be “broken” in the way your current search is.
Hope that helps!