RPM Dependancy Hell

Ok, I installed Redhat 9 from scratch yesterday. I go to do an update and install some new packages (CVS, postgresql, etc) and after sitting and grinding for a while it spits back that "...the following packages were not found on the system, installation cannot continue until they are installed". WTF? This is a newly installed system. Ok, do a bit more checking and not only are both the packages installed, but they have newer versions. So somewhere openssl-devel and krb5-devel (neither of which I can see in the "add / remove applications" program) are either out of date and looking for out of date dependancies, or are on crack and are requesting out of date dependancies.

I thought that RPM Dependancy hell was only for random packages you installed off the internet, not for newly installed systems with no customization done at all. I can run "up2date cvs" to install the individual packages it seems, but still, come on Redhat....