If you alter /etc/sysconfig/selinux and set SELinux strict mode instead of targeted, make sure you don't just reboot!
First, set strict and permissive (just to be sure we can reboot and login again).
Now, before you reboot, touch /.autorelabel. Your system will not successfully reboot if you do not do this! Reboot and watch your apply new system labels on files on the root filesystem.
Reboot again. You should see no more errors except for some .udev related crap. If all goes ok, change 'Permissive' to 'Enforcing' and you should be good to go! Your system is now running on SELinux in Strict mode (and now stuff gets *really* complicated ;-))