Hi, I had the same problem, and thanks to you I got a clue what it's about. I'm pretty sure you did the same thing (I also couldn't resist fidling around with all those new thingies
.
Start -> Control Panel -> Programs and Features -> Turn Windows features on or off (on the left) -> Windows Search (at the bottom).
That should fix it. I don't even use search all that often, but I find the Start Menu search in Win7 the biggest shell/interface improvement yet.