Can you try manually deleting all of the files in the search_index subdirectory of your cache-* directory? Once you've done that, try rebuilding again and let us know how it goes...