Hi
Hast Du auf der Konsole mal ein sudo aptitude autoclean versucht, um die Paketdatenbank zu säubern?
Dann ein sudo aptitude install Name_des_Paketes versuchen.
Fehler 404 bedeutet im Regelfall, das der Server nicht zu erreichen ist.
Stelle auch in den Paketquellen mal von Hauptserver auf Server für Deutschland um oder umgekehrt.
Nächste Frage ist die nach der Version, da ab 7.10 die Unterstützung ausgelaufen ist.
Anderes Problem könnte ein fehlerhafter Xapian-Index sein, so das manche Pakete nicht gefunden werden.
Das behebst Du wie folgt:
sudo update-apt-xapian-index
Dann die Paketdatenbank über synaptic neu einlesen oder gleich weiter auf der Konsole mit:
sudo aptitude update
sudo aptitude upgrade
fakiauso