Why are you trying to install kdelibs3 that is for KDE 2.2.
Code:
[04:48 PM Sat Jun 28: stephen @ ~]
>$ apt-cache policy kdelibs3
kdelibs3:
  Installed: (none)
  Candidate: 4:2.2.2-13
  Version Table:
     4:2.2.2-13.woody.7 0
        500 http://security.debian.org stable/updates/main Packages
     4:2.2.2-13 0
        990 http://ftp.de.debian.org testing/main Packages
As you can see this will remove KDE 3.1 and downgrade the install. you should be installing the packages from testing/unstable.