Usa aptitude y no apt-get, así:
aptitude install kde-full kde-l10n-es
Suerte.
Perdón, creo que es kde-i18n-es. Al menos así era hasta la 3.5.10, con
KDE 4 no me he metido.
Saludos
En KDE4 es kde-l10n-es, y hay que indicarlo en forma explícita, porque
un upgrade no lo selecciona.
Además, si usas kdm para iniciar la consola, tendrás problemas.
Lee los hilos anteriores:
http://lists.debian.org/debian-user-spanish/2009/05/msg00592.html
http://lists.debian.org/debian-user-spanish/2009/05/msg00609.html