I installed the latest iTunes (8?) and once installed the Search functionality in the Start menu stopped working. It only seems to return 'Programs' and 'Files' no matter what I search for. I'm running Beta build 7100.
I did a little googling around an it seems there's a mix of stories for itunes 8 and windows 7. Some good and some bad and some with problems just like yours.. I couldn't see any other fixes apart from re-installing the app or trying compatibility mode..
Maybe there is a 'fix' somewhere or perhaps apple will patch it, i'll keep my eye's open though...
Just a thought...You could try googling for a itunes forum?