Entry not found in index - when searching

After updating our 8.0.2 clients to FP3, we get an error when searching within the “All Documents” view:Server Error: Entry not found in index

The Notes classic version appears to work, but the Notes eclipse version will not. We can work around to some extent by creating an index and choose the option to search by relevance. But the users who wish to sort fields (Who, Date, Size, etc.) cannot.

Notes 8.0.2 FP3

I have tried fixup, updall, design replace, removing the index and recreating it, etc. to fix the issue. One person reported being able to fix by reinstalling the client. I have not been able to verify this and when I tried it on a problem client, that did not solve.