Не раз сталкивался с проблемой, что aptitude при прочих равных, лучше разруливает зависимости пакетов в системе.
Вот и вчера, при минимальной установке debian на сервере, apt-get попросил установить imagemagick как зависимость для mc. Когда попробовал установить mc через aptitude - ничего подобного он не просил. Это еще раз подтверждает, что разработчики не зря рекомендуют использовать именно aptitude вместо устаревшего и не совершенного apt-get.
Да и синтаксис у aptitude проще:
aptitude search mc
aptitude install mc
Тоже самое у apt:
apt-cache search mc
apt-get install mc
Так что в очередной раз убеждаюсь что aptitude лучше.