Comment 6 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.
Do you have some non genuine packages installed which could disturbate the index ? (ppa, ...) or get some errors about wrong rights applied ?