Comment 7 for bug 782953

I think a related, but slightly different issue in 11.10 and 12.04 is Bug #863463. It seems that in newer versions, the Software Center does not actually update the package information (apt-get update), but if one does that manually, it finds new packages without manually calling update-apt-xapian-index.