Did your login screen change? If so I would suggest apt-getting kdm, and maybe removing xdm.

And, are you sure you have all KDE packages? AFAIK Gnome and KDE bite eachother in Debian, the one is compiled with gcc 3.1, the other with 2.9. Library headers changed between these two versions.