I had this problem and the symptom was that the SharePoint Services Search Refresh timer job was in a failed state on one of the servers.  

I fixed it with the following steps:

1) Stop the Windows SharePoint Timer Service
2) Navigate to C:\Documents and Settings\All Users\Application Data\Microsoft\SharePoint\Config
3) Go into the single folder in there that has a GUID type name.
4) You see a whole bunch of XML files and a file cache.ini
5) Copy all the XML files to another folder somewhere (for backup), then delete them but do not delete cache.ini
6) Edit cache.ini to contain just the number "1" in the file - erase whatever is there and replace with "1"
7) Restart the Windows SharePoint Timer Service
8) You should see XML files being regenerated in the folder

Do these steps on all the front-end servers and index/query servers.  In our case on our index & query server the Windows SharePoint Timer Service was jammed in a "stopping" state so we rebooted the server and that cleared it and allowed the SharePoint Services Search Refresh timer job to succeeed. 

It also, as a bonus, finished off the deployment of a WSP solution that had got stuck in the "deploying" state when attempting to deploy.