Sometimes when yum is not updating, or simply not synchronized with the repository, it's a good idea to clean up the cache database and fetch a new list from the server.
yum clean all
mv /var/cache/yum/ /tmp/
mv /var/lib/rpm/__db* /tmp/
rpm --rebuilddb
Somehow I tend to move the files to /tmp/ rather then just remove them, since the rm -rf command is the No. 1 enemy of idiocity.