Start, Search, All Files and Folders has stopped working. Why?

When I click on Start, then Search, then All Files and Folders and search for the name of a file I know is on my computer, the search ends with "Search is complete. No documents to display." I am searching for a file name - not a name contained within a file. I have also seen this tip as a solution:

Install tweakUI from Microsoft, once installed open it and go to the "DESKTOP" tab, scroll down to "Show Search Results". Place an check mark in this box. Somehow there are some progs out there that screw with this setting.

However, when I go to that tab on TweakUI, I do not have a box "Show Search Results".

This is very annoying. Any suggestions would be appreciated. It isn't like I didn't go look first.