Does the spsearch account have admin rights on the domain? It needs to be a member of the local Administrators or Backup Operators group on the machine. If the account is a Domain Admin this will happen automatically. If not, check the local security on the machine to make sure you have placed spsearch in the appropriate groups.
Also, check this registry key to make sure the SPSEARCH account name is listed as a REG_DWORD entry with a value of (1) on the computer that is getting the errors:
"I did RC5, but I didn't flush." - Bill Clinton
"I invented distributed computing." - Al Gore
"I had a dream where every American would be free to run SETI@Home!" - Martin Luther King Jr.
"Greendale is a bodaciously small town, Lane... I can't even Find-A-Drug here!" - Charles De Mar (Better Off Dead)
"I did not have BOINC relations with that woman, Rosetta@Home!" - Bill Clinton