After switching off selinux on a system, i wanted to get rid of some selinux packages too, so i deinstalled a bunch of them. I removed libsepol, and that was a problem, because after removal every app i tried failed because there was no libsepol.so.1 anymore. Even rpm, yum and su couldn't start, so i had to recover via live-cd to get that needed lib back. If so many apps depend on this lib, maybe having a dependeny on them would be ok. But maybe the uninstall of libsepol just did no /sbin/ldconfig after package removal, i couldn't try this by hand, because su didn't work anymore. This is with libsepol-2.0.3-1.fc7
Libsepol is required by libselinux and libselinux is required by a ton of applications. So I do not know how you got rid of libsepol, you must of done an ignoredeps. On rawhide, I see [root@localhost devel]# rpm -q --whatrequires libsepol sysvinit-2.86-17 dump-0.4b41-6.fc8 libsepol-devel-2.0.9-1.fc8 setools-libs-3.2-4.fc8 libselinux-2.0.31-4.fc8 nash-6.0.16-1.fc8 mkinitrd-6.0.16-1.fc8 policycoreutils-2.0.25-12.fc8 [root@localhost devel]# rpm -q --whatrequires libselinux sysvinit-2.86-17 dump-0.4b41-6.fc8 pam-0.99.8.1-6.fc8 shadow-utils-4.0.18.1-17.fc8 nscd-2.6.90-13 setools-libs-3.2-4.fc8 vixie-cron-4.2-2.fc8 setools-console-3.2-4.fc8 dbus-1.1.2-4.fc8 libselinux-python-2.0.31-4.fc8 libselinux-devel-2.0.31-4.fc8 system-config-firewall-tui-1.0.5-4.fc8 openssh-4.7p1-1.fc8 udev-115-2.fc8 PolicyKit-0.5-3.fc8 setroubleshoot-server-1.10.4-1.fc8 bind-chroot-9.5.0-12.a6.fc8 nash-6.0.16-1.fc8 mkinitrd-6.0.16-1.fc8 policycoreutils-2.0.25-12.fc8
With "rpm -q --whatrequires" i get the same ok result as you. I removed libsepol via pirut, maybe this made the difference.