I think I may have had this problem on a previous store but after searching the forums I couldn't find an answer.
I have added a search box to my site and no matter what I type in it comes up saying nothing found. I have just tested with both a simple and advanced search both and neither show any results.
Could you have a quick look and see if it is operator error please. The url is http://brighttights.com/
I have added both types of search box for now to test. Ideally I want the simple search working as this will be only one i plan on using but added the advanced to see if it was a localised problem.