Bingo! (Thanks.)
Note to self: When replacing *important* libraries like libselinux.so, don't just blast the unwanted RPM package away, figuring on then installing the new one. Instead, use --oldpackage or --force to replace the unwanted package with the desired one in atomic operation. Failure to do so will make both rpm and yum (and many other programs) unusable.
--- Vladimir