Listen to what egorgry suggested. One of the first things that I do when installing a Debian system is to install synaptic. This grest utility helps to solve the dependency problems that you are running into. It has a graphical interface that really helps. If you just have a command line right now, installing synaptic will help you get up and running with X, KDE and other apps.
I assume that you are just tring to install KDE, or do you have it up and running already? In other words, did you tell the Debian installer to install KDE, or looking to add development packages in order to compile/add other applications?
Doing apt-get update assures that Debian has the latest packages in it's database, which will save headaches as you go on.