The problem appears to be corruption in the search index. We're still looking into why that happened, but resetting the index appears to have fixed the problem. Unfortunately, that means that that the index started out empty. The indexer is currently processing, but its going to take a while to fill back up.
Kevin