This is a wild guess, but removing gnome may have removed some kde dependencies.
If you remove both of them, and then install kde from the command line, you should get all it's dependencies with it.
Not sure about apt, but if you've left yum intact, it should just be > yum install kde <
|