I updated a CentOS system yesterday from 6.2 to 6.3. I saw it update
selinux-policy-targeted (I think it was) and several hours later, it
still hadn't gotten to the next package; looking, it appeared to be
running a restorecon. I killed it, and redid the update.
For other reasons, it didn't reboot. I brought it up under the most
recent previous kernel, it did an fsck on a 2T drive... then it's been
running autorelabel for at least an hour and a half, and I have no idea
how much longer it will be. It's longer than fsck.
This is a backup server, which uses hardlinks to save space.
You may not consider this a bug, but it certainly makes selinux close
to unusable in anything resembling a working environment.