Bom estive procurando na net como instalar o KDE 4, no Debian, mas o que achei era para deixar o sistema como unstable, o que não gostei muito. Com um pouco mais de buscas achei essa solução no site do KDE, então vamos lá.

Primeiramente, edite seu arquivo /etc/apt/source.list e altere tudo o que estiver como etch/testing para lenny, caso não tenha feito isso.

E adicione essas linhas
##### KDE 4.x #####
deb http://kde4.debian.net/ lenny main

Salve e saia

Agora como root digite:
aptitude update (não estou usando o apt-get, porque gosto do aptitude, ele tem mais opções)

Para instalar o básico do KDE
aptitude install kde4-minimal

Para instalar o KDE completo, que eu fiz
aptitude install kde4

Adicionalmente você pode instalar o pacote de tradução para sua língua nativa o Português do Brasil
aptitude install kde-l10n-ptbr

Eu fiz o seguinte comando
aptitude install kde4 kde-l10n-ptbr

Assim já instalei o KDE 4.1 em português

DICAS:
1 - não faça isso com o KDE rodando, abra um console com CTRL+ALT+F1 e faça esses comandos, pois no meio da instalação ele irá executar o KDM STOP ; KDM START, e daí toda a instalação vai dar erro se você estiver dentro do KDE.

2 - Eu tive que executar o comando aptitude install kde4 duas vezes, na primeira ele não conseguiu instalar tudo de primeira, na segunda ele instalou tudo.

Boa sorte :-)