Try by starting the crawl manually.
Also check the crawl logs.

I was battling with this error  for 3 days last week.
Mostly it won't affect your site  operations except search  feature.

What I ended up doing was to re-build a new SSP.

Of course, you should try to checking Event log and re-configure search service
on the CA first before you rebuild  SSP. Cause rebuilding SSP will need to
re-configure all the settings( profiles, Excel services, BDC, meta data
properties etc)

Has your IT Department tried to do a "Reset all crawled content" this
has been described to me as a last ditch effort but has worked for me
numerous times when my index has become corrupt for whatever reason.

Have you recently migrated any users from one AD to another?

we finally had to rebuild  the SSP like was suggested. But we don't know
what the original reason for the Search Service stopping and getting all messed
up.

No, we have not migrated anything. This is a simple site  that has been running
for over a year without problems.