fuzzy_logic, I may have the answer.
In some late night inspiration I realised it may be one of the 3rd party preference panes I have installed causing the problem. It was.
These are located in /Library/PreferencePanes and ~/Library/PreferencePanes.
I moved them all to temporary subdirectories and restarted System Preferences: spotlight search worked. I then added them back a few at a time, and found that the problem was with SCPlugin (the controller for a utility that integrates Subversion into the Finder).
I don't know if you're using SCPlugin, but if not, maybe it's one of those other little suckers that's causing your problem.
I hope this helps.