Comment 18 for bug 288797

If it matters, I can confirm once more that "sudo update-apt-xapian-index" fixes the problem.
Also I would like to join the opinion that it is a bud with high importance. Package installation is the one thing, which can be expected to be rock solid.