Just my 2 cents:
Bei apt-get jedenfalls gibt's einen Unterschied zwischen den Optionen upgrade und dist-upgrade: Letzteres löscht Abhängigkeiten, wenn die zu installierenden Pakete anders nicht zu installieren sind (was vernünftig ist). (Leider tut dies das grafische Programm update-manager nicht, verwendet also quasi - oder womöglich genau - apt-get upgrade, deswegen kommt es dort manchmal zu solchen "Stillständen"). Bei nur-upgrade blockieren die an sich unnützen Abhängigkeiten schonmal ein Upgrade.
Du hast noch nicht genannt, welches grafische Programm Du verwendet hattest, und ich habe man aptitude noch nicht genau gelesen.
Aber etwas in dieser Richtung wird's wohl sein: Ich selbst mache grundsätzlich und immer
apt-get dist-upgrade