Comment 4 for bug 346612

Confirmed. I had the same problem from a fresh install of Jaunty x64. Updates did not fix the problem.
I followed "Hansip"'s advice ( 'sudo update-apt-xapian-index ' ) and everything seems ok now. :)

PS: note to devel's. The LP site might be fine for you guys, but for us wanting to know the answers, it's very hard to navigate. The only time I made any progress towards the button that should be first up on the "bugs" page, FILE A BUG, (which no where to be seen) was more by mistake, hope and luck, than deliberate. It took me far longer than it should have to end up here.
Otherwise, keep up the good work! :)