The current selinux feature adds an ADD_WRITE for /selinux, but on my system (amd64 with openrc-0.9.9.3 and kernel 3.3.0) it is actually also mounted to /sys/fs/selinux and the system seems to prioritize that (according to sestatus). Adding an exception for /sys/fs/selinux to make.conf fixes it, but the exception should probably be in /usr/portage/features/selinux/profile.bashrc
I ran into this as well on my system (mixed, 3.3.0:hardened-dev).
emerge --info and selinux-base-policy info needs to be added, this should be fixed already in 20120215
*** This bug has been marked as a duplicate of bug 410687 ***