As a double check, see if you can explicitly search by genre:
[Genre]=Rock
(or use Pop or Blues, or Jazz, or some other genre you're fairly sure is in your library.)
If that works, then somehow search isn't using Genre as a default search anymore. You can check to see if it's still set up as a default: Tools > Options > Library & Folders > Manage Library Fields > (go find Genre and click on it) . Then look at the box in the lower left "Default Search Field" and see if it's checked.
On the other hand, it's probably something simple that I'm missing. It seems too strange that this would be unchecked, or that somehow all of your files would suddenly not have a value for genre...
Brian.