Frosty, aptitude и apt-get по-разному зависимости обрабатывают. Ну и aptitude имеет псевдографический интерфейс (на ncurses), можно запустить без аргументов - увидишь.
Вот тут вкратце и на пальцах описана разница в проработке зависимостей
http://www.uofr.net/~alex/wp/?p=77
http://www.psychocats.net/ubuntu/aptitude