Send me please more details, how it happens, and of course your audit.log.

type=1400 audit(1203365995.899:3): avc:  denied  { setsched } for  pid=454
comm="init" scontext=system_u:system_r:init_t:s0
tcontext=system_u:system_r:init_t:s0 tclass=process

are the initial AVCs in question. However, even after making a module that
allows that, the initial setting of keymaps and fonts fail, but no AVC is generated.

There is also:

type=AVC msg=audit(1203544844.064:9322): avc:  denied  { sendto } for  pid=1
comm="init" path=002F636F6D2F7562756E74752F757073746172742F32343833
scontext=system_u:system_r:init_t:s0
tcontext=unconfined_u:unconfined_r:unconfined_t:s0-s0:c0.c1023
tclass=unix_dgram_socket

However, for this we probably want to actually have policy for initctl (the
sender, running as unconfined_t in this example.

OK, so the sum total of stuff to get this working appears to be:

Random
------
allow init_t self:process setsched;

initctl defs:
# cat initctl.fc 

/sbin/initctl	--	gen_context(system_u:object_r:initctl_exec_t,s0)

[root@localhost ~]# cat initctl.if

## <summary>policy for initctl</summary>

########################################
## <summary>
##	Execute a domain transition to run initctl.
## </summary>
## <param name="domain">
## <summary>
##	Domain allowed to transition.
## </summary>
## </param>
#
interface(`initctl_domtrans',`
	gen_require(`
		type upstart_initctl_t;
                type initctl_exec_t;
	')

	domtrans_pattern($1,initctl_exec_t,upstart_initctl_t)
')


########################################
## <summary>
##	Execute initctl in the initctl domain, and
##	allow the specified role the initctl domain.
## </summary>
## <param name="domain">
##	<summary>
##	Domain allowed access
##	</summary>
## </param>
## <param name="role">
##	<summary>
##	The role to be allowed the initctl domain.
##	</summary>
## </param>
## <param name="terminal">
##	<summary>
##	The type of the role's terminal.
##	</summary>
## </param>
#
interface(`initctl_run',`
	gen_require(`
		type upstart_initctl_t;
	')

	initctl_domtrans($1)
	role $2 types upstart_initctl_t;
	allow upstart_initctl_t $3:chr_file rw_term_perms;
')

[root@localhost ~]# cat initctl.te
policy_module(initctl,1.0.0)

########################################
#
# Declarations
#

type upstart_initctl_t;
type initctl_exec_t;
application_domain(upstart_initctl_t, initctl_exec_t)
role system_r types upstart_initctl_t;


########################################
#
# initctl local policy
#

gen_require(`
	type init_t;
	type user_tmp_t;
')

## internal communication is often done using fifo and unix sockets.
allow upstart_initctl_t self:fifo_file rw_file_perms;
allow upstart_initctl_t self:unix_stream_socket create_stream_socket_perms;
allow upstart_initctl_t self:unix_dgram_socket create_socket_perms;
allow upstart_initctl_t init_t:unix_dgram_socket sendto;
allow init_t upstart_initctl_t:unix_dgram_socket sendto;

files_read_etc_files(upstart_initctl_t)

libs_use_ld_so(upstart_initctl_t)
libs_use_shared_libs(upstart_initctl_t)

miscfiles_read_localization(upstart_initctl_t)

optional_policy(`
	gen_require(`
		type sysadm_t;
		type sysadm_devpts_t;
		type sysadm_tty_device_t;
		role sysadm_r;
	')

	initctl_run(sysadm_t, sysadm_r, { sysadm_tty_device_t sysadm_devpts_t })
')

optional_policy(`
	gen_require(`
		type unconfined_t;
		type unconfined_devpts_t;
		type unconfined_tty_device_t;
		role unconfined_r;
	')

	initctl_run(unconfined_t, unconfined_r, { unconfined_tty_device_t
unconfined_devpts_t })
')

There's still some weirdness (initctl wants to setuid, which looks wrong), but
it's good enough for now. I'd rather use 'initctl_t' instead of
'upstart_initctl_t', but initctl_t is taken for the crappy /dev/initctl socket. :)

Why not just label it initrc_t?

/sbin/initctl	--	gen_context(system_u:object_r:initrc_exec_t,s0)

Well, it's not really an init *script* ; it's just something that signals init
to start/stop things, and report on status. It's sort of like /sbin/service,
execept it talks to the daemon itself over sockets instead of just wrapping
other scripts.

Policy added by Dan in selinux-policy-3.3.0-1.fc9.