/etc/rc.d/rc.sysinit uses restorecon, but does not require either /sbin/restorecon by file name, or policycoreutils by package or feature. This is invisible with normal installations, but I did an upgrade from FC3 and received some errors at reboot after that. P.S. Both restorecon and /sbin/restorecon are used, which is inconsistent.
Tools are are required by the policy. I believe you're seeing bug 153100. *** This bug has been marked as a duplicate of 153100 ***