Oops more replies while I was typing and tending to other fires.

If you want to go for KDE again just go to synaptic and search for kde. That should pull in all the packages needed for a KDE desktop. I always add kdm, which is the equivalent of gdm, but since it's newly installed it'll ask you which desktop environment to boot.

NOTE: I haven't done this since upgrading to Hardy from Gutsy.