Gestern, war ich wirklich fast am verzweifeln. Nach dem Hinzufügen einer neuen Paketquelle und dem folgendem apt-get update wollte das gewünschte Paket einfach nicht in der Liste auftauchen. Das lustige in der Konsole mit apt-cache serach war es zu finden und auch ohne Probleme zu installieren. Nach ein wenig suchen hab ich dann die Lösung gefunden.
sudo update-apt -xapian -index baut recht schnell einen neuen Index auf, der dann wieder auf dem aktuellen Stand ist.