I recently upgraded from 2.3.x to 2.5.1. I've only just noticed that the in-built search facility no longer works - it worked a treat pre-upgrade. I get no results on the blog itself, or using the Search Posts button on the Manage/Posts page.
I'm not running any search plug-ins, just the "vanilla", straight-out-of-the-box one. I have another blog also on 2.5.1 that works no problem.
Blog address: http://www.moshtour.me.uk