Obwohl ich durch das viele Rumprobieren jetzt tatsächlich auch von der "Magie von Aptitude" überzeugt bin, hab ich das in diesem speziellen Fall so ganz einfach gelöst bekommen.
Hab es jetzt so gemacht, dass ich mir von apt-show-versions alle Pakete hab anzeigen lassen, die als "newer than version in archive" gekennzeichnet waren und diese manuell deinstalliert habe. Anschließend habe ich ohne kdenext alles neu installiert, was dabei so entfernt wurde. Keine schöne Lösung, scheint aber funktioniert zu haben.
Danke jedenfalls für eure Hilfe!
