Visit the http://kde-redhat.sourceforge.net/ page, which offers a procedure for using apt-get to install kde 3.1 on redhat, and automatically work out all the dependencies.
Problem: Apt-get will complain about all "duplicate" entries in your rpm database. I found that using up2date to install redhat updates introduces those duplications.
For every duplication, do an rpm -q and you'll see their are duplicate entries.
I manually did an "rpm --justdb -e --nodeps" for each of them, pointing at the "older" entry. When I'd gone through the lot (I ended up having to use this procedure for *every* package up2date had touched), the procedure on the sourceforge page worked great.
I have to hand it to the kde people, for their humility. Calling this "3.1" rather than "4.0". It's such an improved desktop!