Wenn die Schnellsuche in Synaptic fehlt:
sudo apt-get install apt-xapian-index
sudo apt-get install apt aptitude synaptic --reinstall

Nach einem Systemneustart steht die Schnellsuche zur  Verfügung.

Wenn die Erstelling des Index sehr lange dauert, hilft ein:
sudo update-apt-xapian-index