Al intentar ejecutar la instalación de un paquete con aptitude, éste responde que necesita eliminar muchos paquetes. Esto es debido a que aptitude, a diferencia de ap-get, busca incongruencias de dependencias de paquetes e intenta solventarlas. Por ejemplo, me faltaba el paquede kde, kdeaddons y kdepim, y al intentar instalar el debian-keyring salía lo siguiente:

# aptitude install debian-keyring
Leyendo lista de paquetes… Hecho
Creando árbol de dependencias… Hecho
Leyendo la información de estado extendido
Inicializando el estado de los paquetes… Hecho
Escribiendo información de estado extendido… Hecho
Leyendo las descripciones de las tareas… Hecho
Construir la base de datos de etiquetas… Hecho
Los siguientes paquetes no se usan y se ELIMINARÁN:
akregator amor ark arts artsbuilder atlantik atlantikdesigner blinken cervisia cvs dcoprss dirmngr dosfstools edict eyesapplet
fifteenapplet flac gnuift gnuift-perl gnupg-agent gnupg2 gpgsm imlib-base imlib11 indi juk kaboodle kaddressbook-plugins kalarm kalzium
kalzium-data kanagram kandy kanjidic kappfinder karm kasteroids kate-plugins katomic kaudiocreator kbackgammon kbattleship kblackbox
kbounce kbruch kbstate kcalc kcharselect kcoloredit kcron kdat kde-amusements kde-core kde-icons-mono kdeaccessibility
kdeaddons-kfile-plugins kdeadmin kdeadmin-kfile-plugins kdeartwork kdeartwork-emoticons kdeartwork-misc kdeartwork-style
kdeartwork-theme-icon kdeartwork-theme-window kdebase kdeedu kdeedu-data kdegames kdegames-card-data kdegraphics
kdegraphics-kfile-plugins kdelibs kdelirc kdemultimedia kdemultimedia-kappfinder-data kdemultimedia-kfile-plugins kdenetwork
kdenetwork-filesharing kdenetwork-kfile-plugins kdepasswd kdepim-kfile-plugins kdepim-kresources kdepim-wizards kdessh kdetoys kdeutils
kdewallpapers kdewebdev kdf kdict kdm kdnssd kdvi kedit keduca kenolaba kfax kfaxview kfilereplace kfloppy kfouleggs kgamma kget
kgoldrunner kgpg khangman khexedit kicker-applets kiconedit kig kimagemapeditor kitchensync kiten kjots kjumpingcube klaptopdaemon
klatin kleopatra klettres klettres-data klickety klines klinkstatus kmag kmahjongg kmailcvt kmid kmilo kmines kmix kmoon kmousetool
kmouth kmplot kmrml knetwalk knetworkconf knewsticker knewsticker-scripts knode knotes kodo kolf kolourpaint kommander konq-plugins
konquest konsolekalendar kontact kopete korganizer korn kpackage kpager kpat kpdf kpercentage kpf kpilot kpoker kpovmodeler kppp krdc
krec kreversi krfb kruler ksame ksayit kscd kscreensaver kscreensaver-xsavers kshisen ksig ksim ksirc ksirtet ksmiletris ksnake
ksnapshot ksokoban kspaceduel kstars kstars-data ksvg ksync ksysv ktalkd kteatime ktimer ktip ktnef ktouch ktron kttsd ktuberling
kturtle ktux kuickshow kuser kverbos kview kviewshell kvoctrain kwalletmanager kweather kwifimanager kwin4 kwordquiz kworldclock
kxsldbg libarts1-audiofile libarts1-mpeglib libarts1-xine libboost-python1.33.1 libconvert-binhex-perl libcrypt-ssleay-perl
libcvsservice0 libdate-manip-perl libdb4.3++c2 libfinance-quote-perl libfont-afm-perl libgadu3 libgle3 libgnuift0c2a libgsmme1c2a
libhtml-format-perl libhtml-parser-perl libhtml-tableextract-perl libhtml-tagset-perl libhtml-tree-perl libindex0 libio-socket-ssl-perl
libio-stringy-perl libjpeg-progs libkdeedu3 libkdegames1 libkgantt0 libkiten1 libkpimexchange1 libksba8 liblockdev1 libmailtools-perl
libmeanwhile1 libmime-perl libmrml1c2a libnet-ssleay-perl libnews-nntpclient-perl libparse-yapp-perl libpoppler0c2-qt libpth20 librss1
libt1-5 libtidy-0.99-0 libtiff-tools libtimedate-perl libtunepimp-bin liburi-perl libwww-perl libxml-dom-perl libxml-handler-trees-perl
libxml-libxml-common-perl libxml-libxml-perl libxml-namespacesupport-perl libxml-parser-perl libxml-perl libxml-regexp-perl
libxml-sax-expat-perl libxml-sax-perl libxml-writer-perl libxml-xql-perl lilo-config lisa lskat mpeglib ncompress networkstatus noatun
noatun-plugins perl-tk pinentry-curses pinentry-qt qca-tls quanta quanta-data superkaramba talk tetex-base tetex-bin tetex-doc
tex-common tidy ttf-dustin ttf-kochi-gothic ttf-sjfonts vorbis-tools xli xscreensaver xscreensaver-gl ytalk zoo
Se han retenido los siguientes paquetes:
linux-image-2.6.18-4-486 linux-image-2.6.18-4-686
0 paquetes actualizados, 0 nuevos instalados, 301 para eliminar y 2 sin actualizar.
Necesito descargar 0B de ficheros. Después de desempaquetar se liberarán 573MB.
¿Quiere continuar? [Y/n/?] n
Cancela.

Es decir, comprueba que faltan paquetes de los que dependen todos los anteriores e intenta eliminar posibles problemas de dependencias eliminándolos.

Una vez instalados los paquetes correspodientes, funciona correctamente:

aptitude install kde
Leyendo lista de paquetes… Hecho
Creando árbol de dependencias… Hecho
Leyendo la información de estado extendido
Inicializando el estado de los paquetes… Hecho
Escribiendo información de estado extendido… Hecho
Leyendo las descripciones de las tareas… Hecho
Construir la base de datos de etiquetas… Hecho
Se instalarán automáticamente los siguientes paquetes NUEVOS:
kdeaddons kdepim
Se han retenido los siguientes paquetes:
linux-image-2.6.18-4-486 linux-image-2.6.18-4-686
Se instalarán los siguiente paquetes NUEVOS:
kde kdeaddons kdepim
0 paquetes actualizados, 3 nuevos instalados, 0 para eliminar y 2 sin actualizar.
Necesito descargar 46,2kB de ficheros. Después de desempaquetar se usarán 176kB.
¿Quiere continuar? [Y/n/?] y
Escribiendo información de estado extendido… Hecho
Des:1 ftp://ftp.de.debian.org etch/main kdeaddons 4:3.5.5-1 [17,7kB]
Des:2 ftp://ftp.de.debian.org etch/main kdepim 4:3.5.5.dfsg.1-6 [20,8kB]
Des:3 ftp://ftp.de.debian.org etch/main kde 5:47 [7714B]
Descargados 46,2kB en 7s (6378B/s).
Seleccionando el paquete kdeaddons previamente no seleccionado.
(Leyendo la base de datos …
169657 ficheros y directorios instalados actualmente.)
Desempaquetando kdeaddons (de …/kdeaddons_4%3a3.5.5-1_all.deb) …
Seleccionando el paquete kdepim previamente no seleccionado.
Desempaquetando kdepim (de …/kdepim_4%3a3.5.5.dfsg.1-6_all.deb) …
Seleccionando el paquete kde previamente no seleccionado.
Desempaquetando kde (de …/archives/kde_5%3a47_all.deb) …
Configurando kdeaddons (3.5.5-1) …
Configurando kdepim (3.5.5.dfsg.1-6) …
Configurando kde (47) …

#aptitude install debian-keyring
Leyendo lista de paquetes… Hecho
Creando árbol de dependencias… Hecho
Leyendo la información de estado extendido
Inicializando el estado de los paquetes… Hecho
Escribiendo información de estado extendido… Hecho
Leyendo las descripciones de las tareas… Hecho
Construir la base de datos de etiquetas… Hecho
Se han retenido los siguientes paquetes:
linux-image-2.6.18-4-486 linux-image-2.6.18-4-686
0 paquetes actualizados, 0 nuevos instalados, 0 para eliminar y 2 sin actualizar.
Necesito descargar 0B de ficheros. Después de desempaquetar se usarán 0B.
Escribiendo información de estado extendido… Hecho