I recently asked this same question on the Debian forum, maybe the responses I received will answer your question.
I found that 'apt-get remove kdm' did not remove everything, and the best way to do it was by using aptitude (it should be in the Debian menu of GNOME or just run '$ aptitude'). Select KDE and hit '-' and then 'g' to remove it. You can scroll through the list of packages that are to be removed and make sure those are the ones you want gone.
Hope that helps.
EDIT: By the way, that other thread is here