I had/have the same problem in Fedora. I try to install a package that has dependencies, and it says that it can't find those dependencies installed. I try to install them and it says that they are already installed.
I am able to continue by installing them all at the same time. I usually do this with the rpm command, but should work with yum as well. Try this:
yum install libselinux dbus krb5-libs pam libxml2 [package you initially wanted to install]
I hope that this helps.