I just tried to run a yum update, but ran into this:

I remember these libs caused me a lot of problems when I was installing VLC, but I somehow solved that. How, I have no idea anymore.
Anyhow, I went into the /usr/lib folder, and sure enough, they, and the files they link to, are there. I guess that's why they are being detected by system-install-packages, but why yum can't find them, I have no idea.

As you might have figured out by now, I'm confused. Does anyone know what the correct procedures to solve this kind of problem are?

did you compile them from source or rpms. if it was source then there not in the rpm database. I'm not running a rpm distro right now so I cant be more help.

Obtained them as rpms.

are you using FC3 rpms dont mix rpms from other disros or older versions of your distro. also happens when you have alot of different you sources.

I remember obtaining the FC3 rpm from rpm.pbone.net. I cannot recall the process, since it was long ago, but I might have forced the install of one of them, because I recall that the two rpms needed were apparently dependant on each other, leading to a rather stupid dependency circle, meaning that there seemed to be no other way to install them, other than forcing one of them.

I think when you get that two rpms depend on each other install both rpms on the same line.

example rpm -ivh file1xxx.rpm file2.xxx.rpm

The only way I can see out of your dependency hell is to uninstall all of the problem rpms. then try www.freshrpms.net