Не раз сталкивался с проблемой, что aptitude при прочих равных, лучше разруливает зависимости пакетов в системе. Вот и вчера, при минимальной установке debian на сервере, apt-get попросил установить imagemagick как зависимость для mc. Читать дальше