Que rama de debian usas?
Suponiendo que uses Sarge (sé que en Sid está el KDE 3.5 pero no puedo asegurar si en Etch también) deberías instalar el KDE 3.5 desde los backports de sarge:
deb
http://www.backports.org/debian/ sarge-backports main
Luego un simple
Código:
apt-get update && upgrade
Salu2