You probably need to replace the search.bundle file in system/library/coreservices. You may also need to replace systemuiserver.app in the same folder. The latter can be extracted from the 10.4.5 combo update, however search.bundle is not a complete file in that update, so you will have to get it from elsewhere. Send me a PM with your email, and I can send you that file.
It's really not big problem and the solution is pretty simple. It is kind of a scare at first though. The old Front Row should work fine, by the way.