Ein Freund hat mich vor Kurzem um Rat gefragt, da er eine Installation eines Ubuntu-Ablegers für ein Resourcen-armes System zurechtstutzen wollte und ihm dabei die Abhängigkeiten der Pakete in den Weg kamen. Ich arbeite meist mit aptitude auf Debian-basierten Systemen, komme daher mit diesem Werkzeug am besten zurecht um solche Abhängigkeits-Probleme zu lösen und habe ihm einige Tips dazu gesendet:

Ich arbeite immer noch am liebsten mit dem ncurses-basierten Tool "aptitude" auf debian-artigen Systemen.
Manchmal gibt es gemeine Kombinationen, so hatte man bei Debian früher mal das Problem, dass ssh-server über eine optionale Abhängigkeit xorg nach sich zog. Sollte Dir so etwas die Pakete beim updaten wieder installieren wollen, kannst Du das unerwünschte Paket auf "hold" setzen:
debian.org/doc/manuals/debian-…

Bei Ubuntu und seinen Ablegern gibt es ein bestimmtes Paket welches darüber entscheidet, welchen Desktop, respektive welche Ubuntu-Variante Du installiert hast und welches bei Dir vermutlich diese Abhängigkeiten verursacht. Bei Ubuntu ist das der "ubuntu-desktop", bei Kubuntu der "kubuntu-desktop", bei Lubuntu der "lubuntu-desktop" und sicher hast Du das Muster bereits erkannt. Dieses kann gefahrlos entfernt werden, da die davon gepullten Pakete werden nicht als abhängig definiert und können dann nach Bedarf manuell entfernt werden, wie Du es bereits versucht hast.

Es kann zu Problemen beim Upgrade auf die nächste Version führen dieses Paket zu entfernen, da dann neue, für das booten essentielle, Pakete nicht automatisch installiert werden. Es empfiehlt sich daher dieses Paket während einem dist-Upgrade wenn möglich wieder hinzuzufügen und gleich wieder abzuwählen um zu sehen, welche Pakete es installiert hätte.

Beim arbeiten mit aptitude kannst Du das update prüfen, bevor es angewendet wird: Drücke [U] um die Paketliste zu aktualisieren, [shift]+[U] wählt dann alle Updates und deren Abhängigkeiten aus. Danach kannst Du mit [G] zur Vorschau wechseln und allenfalls nicht erwünschte Pakete mit [_] zum Entfernen markieren und per [shift]+[0] (=) den Zustand fixieren (das oben erwähnte "hold"). Bist Du in der Vorschau zufrieden, kannst Du nochmals [G] drücken um die (de)installation zu starten.

Wenn Du Konflikte verursachst erscheint ein roter Balken und Du kannst die Konfliktansicht mit [E] betreten um die Problempakete zu untersuchen und zu entscheiden was damit passiert.

Falls Du ein Durcheinander mit den Paketen bekommst, kannst Du über das Menü auch alle aktuelle geplanten Änderungen verwerfen und nochmals neu beginnen.

Allgemein navigiert man in aptitude mit den Pfeiltasten, bei graphischen Terminals auch mit der Maus. Mit [Enter] öffnest Du das
markierte Element, [Escape] bringt Dich wieder einen Schritt zurück, auch über mehrere Schritte, wenn gewünscht.

Ach ja, und aptitude beisst sich nicht mit apt-get oder dem GUI-Updater, da die alle nur Frontends für dpkg sind. Es kann aber stets nur eines dieser Werkzeuge gleichzeitig laufen, Du musst den GUI-Updater also unter Umständen schliessen, wenn es die Paket-Verwaltung blockiert (was Dir aptitude sagen würde).