I've found a couple of issures with my SELinux backports. One is actually a bug present in sysvinit and cron (at least):

The debian/rules makefiles uses dpkg-architecture to detect a Linux system (as opposed to GNU hurd or FreeBSD or Solaris) since SELinux only works on Linux. This code queries the DEB_HOST_ARCH_OS variable via dpkg-architecture, but this variable isn't available on sarge (yet)...

When building with either my dpkg backport or by using code similar to the following:

dpkg-architecture -qDEB_HOST_ARCH_OS || dpkg-architecture -qDEB_HOST_GNU_SYSTEM

the packages will actually have SELinux support enabled.

I've already filed a bug against sysvinit, but should I also file bugs against logrotate and cron, who apparently use the same code to detect SELinux?

(openssh and coreutils have better fallback code than suggested above in place)