Working on a fresh local install of MOSS I ran into this error today while trying to crawl a BDC data source:
I had been having some real trouble with my SSP earlier in that day, and my first thought was that I was going to have to create a new SSP, but then I realized the issue was actually something embarrassingly simple.
Check your default content access account, and the account your Office Sharepoint Server Search service is running under. Local Service is not sufficient!!!
I hope this helps someone else!