The reason psi wanted to remove kde was that there was a conflict, and you were telling him to install psi. I'm sure APT asked if it was okay, and you said yes go ahead (without thinking, or else ran it with the -y flag). Because APT is powerful, it's somewhat dangerous. I've gotten into the habit of running a simulation first for packages I'm not sure of. Just enter "apt-get -s install packagename" and look to see what the results would be.
Edit: note that the kde metapackage is not the same thing as KDE itself.
The kde metapackage in testing has broken dependencies at the moment. When I did a fresh install of testing recently, it wouldn't install kde. So there wasn't any chance for you to use "apt-get install kde" successfully. Instead, you could have installed kde-core and a few important kde programs, and those dragged the majority of useful kde packages with them. I think only Sid (unstable) is using KDE 3.5 at the moment.
I wouldn't necessarily reinstall at this point. Play with the system and see if you can get it working again as good practice and learning to understand your system and APT. Print out and read the APT how-to in my sig.
I'm guessing that Evolution, like Thunderbird and other programs, stores all of your stuff under your home directory. But for goodness sakes, find out for sure and back it up.
It isn't really recommended to run testing unless you "know what you're doing." Personally, I've installed a purely stable version and in parallel am running testing, to learn the ropes. Until I'm confident running testing, I am keeping my main stuff on stable.