Not really my area of expertise, but seeing as you havent had too many responses, though I might "kick start" some conversation....
You sure osearch is up and running - stsadm -o spsearch -action start
Have a look at :
http://social.technet.microsoft.com/Forums/en-US/sharepointsearch/thread/72c4be66-a77a-438d-8c39-b69e675fb5feAnd for something slightly more obscure - one user reported having to do a backup and restore :
http://social.technet.microsoft.com/Forums/en-US/sharepointadmin/thread/97ef0fce-d51a-43d0-9e99-24818296d7c9