grub needs to be allowed execmem (and used to be) avc: denied { execmem } for comm="grub" egid=0 euid=0 exe="/sbin/grub" exit=-13 fsgid=0 fsuid=0 gid=0 items=0 pid=9454 scontext=system_u:system_r:unconfined_t:s0 sgid=0 subj=system_u:system_r:unconfined_t:s0 suid=0 tclass=process tcontext=system_u:system_r:unconfined_t:s0 tty=pts4 uid=0
Currently grub (bootloader_t) has execmem but we do not have a transition from unconfined_t. It only transitions from init. But it looks like this is true in FC7 and Rawhide. I will add the transition back to rawhide. I believe there were other problems with this transition in the past and that is why I turned it off, but I will turn it back on and see what happens. Fixed in selinux-policy-3.0.3-1.fc8
Should be fixed in the current release