Corruption with RPMs/unable to reslove dependencies for -actually installed- software

[Ferindo Middleton Jr]

I just downloaded FC4 and I had to go back and install some packages I 
chose not to during the installation.

However, it seems that the RPM database is corrupted or not jiving well 
or something because when I use the Desktop > System Settings > 
Add/Remove Applications to install some of the bundled packages with 
FC4, I get a message saying that RPM "Packages Not Found" but if I try 
to 'yum install <package-name>' yum says "Nothing to do" and if I 'rpm 
-q <package-name>' RPM returns the 'package-and-version'... So why does 
RPM say it can't find the package when resolving the dependency to  the 
package.

I've tried rpm --rebuilddb but that doesn't seem to fix the issue

Any ides for how to fix this?

Ferindo