Apenas esbarrei nisto-- Reiniciando depois que eu atingi esse ponto e, em seguida, executando novamente a instalação parece ter tomado cuidado com isso.
$ sudo apt get install selinux
<snip>
usr/sbin/semodule: SELinux policy is not managed or store cannot be accessed.
Error opening /etc/selinux/ubuntu/contexts/files/file_contexts.local: No such file or directory
libsemanage.sefcontext_compile: sefcontext_compile returned error code 255. Compiling /etc/selinux/ubuntu/contexts/files/file_contexts.local
libsemanage.semanage_install_active: Could not copy /etc/selinux/ubuntu/modules/active/policy.kern to /etc/selinux/ubuntu/policy/policy.29. (No such file or directory).
/usr/sbin/semodule: Failed!
dpkg: error processing package selinux (--configure):
subprocess installed post-installation script returned error exit status 1
Errors were encountered while processing:
selinux
E: Sub-process /usr/bin/dpkg returned an error code (1)
$ sudo reboot
$ sudo apt-get install selinux
Reading package lists... Done
Building dependency tree
Reading state information... Done
selinux is already the newest version.
0 upgraded, 0 newly installed, 0 to remove and 0 not upgraded.
1 not fully installed or removed.
After this operation, 0 B of additional disk space will be used.
Do you want to continue? [Y/n]
Setting up selinux (1:0.11) ...
Generating grub configuration file ...
Found linux image: /boot/vmlinuz-3.13.0-30-generic
Found initrd image: /boot/initrd.img-3.13.0-30-generic
Found linux image: /boot/vmlinuz-3.13.0-24-generic
Found initrd image: /boot/initrd.img-3.13.0-24-generic
Found memtest86+ image: /boot/memtest86+.elf
Found memtest86+ image: /boot/memtest86+.bin
done
* Starting SELinux autorelabel [ OK ]
Processing triggers for initramfs-tools (0.103ubuntu4.2) ...
update-initramfs: Generating /boot/initrd.img-3.13.0-30-generic
$ sestatus
SELinux status: enabled
SELinuxfs mount: /sys/fs/selinux
SELinux root directory: /etc/selinux
Loaded policy name: ubuntu
Current mode: permissive
Mode from config file: permissive
Policy MLS status: enabled
Policy deny_unknown status: allowed
Max kernel policy version: 28
Já faz um tempo desde que eu joguei com o SELinux (e nunca em uma distro baseada no Debian), mas meu palpite é que a instalação depende de algo que não está rodando no kernel por padrão e a reinicialização cuida disso.