Comment 3 for bug 971864

This issue seems to be due to a problem with the file /var/lib/apt-xapian-index/cataloged_times.p -- perhaps it's an invalid value or some file corruption that is resulting in the cPickle.load command failing to deserialise the file.

In my case I simply renamed this file, re-ran the index process (sudo /usr/sbin/update-xapian-index -u -f) and the issue appears to be resolved. I'll need to leave it a few days to let this run through cron in order to be completely sure.