SELinux blocks access to device files when booting 2.6.32.* kernels (fc12)

[Karl-Michael Schneider]

I cannot boot any 2.6.32.* kernel, right after udev is started I see
console messages like

ln: creating symbolic link "/dev/fd": Permission denied

and then booting is very slow and mounting the local file systems
fails. I believe it is a problem with SELinux because when I add
enforcing=0 to the kernel parameters in grub, it boots with no
problems, although I see many console messages like

udev-work[678]: setfilecon /dev/fd failed: Operation not supported

I also have a 2.6.31.12-174.2.22 kernel installed which I can boot and
which doesn't have this problem. But every newer kernel that I
installed does not boot when SELinux is enforcing.

I relabeled the filesystem, but it didn't help.

Any ideas what I can try next?