My Fedora 9 box cannot boot without selinux=0. It was a nightmare doing a http install only to find it was referring to non-existent selinux policy files. I booted by selinux=0 and then a yum update solved some of the problems but now it cannot boot without selinux=0.
[fcuser@Vandaman ~]$ rpm -qa | grep selinux libselinux-python-2.0.67-4.fc9.i386 selinux-policy-devel-3.3.1-103.fc9.noarch libselinux-2.0.67-4.fc9.i386 selinux-policy-3.3.1-103.fc9.noarch
Regards, Vandaman.