Recientes actualizaciones en Fedora 13 introdujeron algunos pequeños bugs, los cuales afectarían al sistema de forma que este no reportara nuevas actualizaciones, y por ende el usuario no se enteraría  ni aplicaría nuevas actualizaciones en paquetes.
Los fix para este problema están en los repos desde el 22 de julio, y para aquellos que hayan hecho un update manual ya deberían de tenerlos solventados.

Para solucionar este problema se debe actualizar de forma manual, abrir una terminal y ejecutar

su -c "yum -y --skip-broken update"

para correr las actualizaciones, o  

su -c "yum -y --skip-broken update gnome-packagekit selinux-policy"

para solventar solo este bug mencionado, luego de actualizar, deben reiniciar la PC para que se apliquen los cambios.

Más information: Package update notifications fixed