Some hints :-)
Ohhhkay. I really should write this down the next time I do it, because it's always a hassle. However, I didn't.
Now, I'm positive there's a better way to do this, but since I kept getting errors, I just kept downloading packages until it worked. Here are all the packages I eventually had upgraded:
Fun huh? Those packages are about 88 megs total. You probably don't need all of them, but these are the ones I ended up needing to get. I first used the --force option with rpm. HOWEVER, be careful, since your KDE will be BROKEN until you get the new one installed!!! Use rpm -e with --force AT YOUR OWN RISK. :-)
Basically, once I had all these packages, I just started doing rpm -Uvh <package name> until I got everything installed. Every so often, it would say something like "blah is needed by whatsit" so I would install that package first. Actually -- who knows: if you have all the above packages, you might be able to just go "rpm -Uvh *", but I didn't at the time, so I had to install many of them by hand.
If you have RedHat 7.2, I recommend you get the packages from the RedHat Skipjack beta distro, as this will fit in a little better with your RedHat setup.
Disclaimer: This worked for me, BUT MAY NOT WORK FOR YOU. Try at your own risk! I am now happily running KDE 3 on RedHat 7.2. I've got to tell you: listening to mp3's NEVER was this good! Holy moley! I'm liking KDE 3, although I"m also getting some strange system lockups. Hopefully not related.
Good luck! It's kind of a pain, but I think it's worth it.