Information
Configure SELINUX to be enabled at boot time and verify that it has not been overwritten by the grub boot parameters.
Rationale:
SELinux must be enabled at boot time in your grub configuration to ensure that the controls it provides are not overridden.
Solution
Edit /boot/grub/menu.lst and remove all instances of selinux=0 and enforcing=0 on all kernel lines.
Additional Information:
This recommendation is designed around the grub bootloader, if LILO or another bootloader is in use in your environment enact equivalent settings.