[PhilB]

Попробуйте для начала переустановить aptitude. Удаляете пакет, качаете пакет вручную из репов и ставите dpkg -i.

[ruslandh]

Так-как apt более глубоко считает зависимости - возможно проблема не в этом.
Второе подозрение - что у вас назначено слишком много репозиториев для обновления и apt не может обработать их.
Что-то подобное :


http://www.altlinux.org/Apt/TroubleShooting
Превышение числа пакетов

[El Scorpio]

А как команда sudo apt-get update отрабатывается?

Как это починить?»

Команда sudo apt-get install -f либо доустановит пропавшие пакеты, либо удалит лишние (например, из отключенного репозитория)