Añadimos el siguiente repositorio en apt, como siempre editando el archivo /etc/apt/sources.list

deb http://pkg-kde.alioth.debian.org/kde-3.5.0/ ./

Luego un

#apt-get update
#apt-get upgrade
#apt-get dist-upgrade

Tener cuidado, porque puede que algunos programas que uséis en kde no este pasado a kde 3.5, y lo tengáis que desinstalar para instalar kde-3.5.