Upstart doesn't support SELinux (look at https://lists.ubuntu.com/archives/upstart-devel/2007-July/000440.html for a way to make this work), so sudo aptitude install sysvinit to replace upstart with a normal, SELinux-friendly init script). You'll be asked to remove ubuntu-minimal - this is okay. If you undo this later, reinstall ubuntu-minimal.
First, you have to boot into an selinux-enabled kernel. Using your favorite text editor (probably Vim, right?), open up /boot/grub/menu.lst. Then add, to the end of the kernel line of the first kernel, "selinux=1 enforcing=0". Or, optionally, you can copy the first one, paste the entry in the appropriate place above (being careful about where Ubuntu does and does not what you to put custom boot stanzas), and add selinux=1 enforcing=0 to the copy instead . Now, you must reboot so that you're in an selinux-enabled kernel. Right now, you're only in a kernel with support compiled in, not turned on. Next, install selinux-default-policy (selinux-basics on Gutsy), either with aptitude or synaptic. Finally, upstart's /bin/init isn't SELinux-enabled. So, you want to aptitude get install sysvinit - at this point, you should reboot... Hopefully, sysvinit scripts work for you. It broke on my first reboot, worked on the second (because init is replaced). Use ls -Z to see if your files are appropriately labeled, and you're done. If you find your files aren't appropriately labeled, try relabelling your filesystem with: sudo fixfiles relabel /