Comment 7 for bug 1533554

>Never met such issue with the actual (nor prior) 0.83
>I suppose the xapian index is borked; i propose to purge (complete removal) both synaptic and apt-xapian-index, then reinstall them.

Yes, did both those on each machine.

> Do you have some non genuine packages installed which could disturbate the index ? (ppa, ...) or get some errors about wrong rights applied ?

No to those. As said, it happens on a clean install with no 3rd party sources, as well as upgraded machines.