Existe um Link simbólico errado (bug confirmado).
Esses comandos resolveram o problema, no meu caso.
sudo mv /var/cache/app-info/xapian/default /var/cache/app-info/xapian/default_old
sudo mv /var/cache/app-info/xapian/default_old /var/cache/app-info/xapian/default
Acho que dar permissões completas a uma pasta de banco de dados de software não é uma boa ideia.
Você pode precisar fazer isso toda vez que adicionar um novo repositório.