Could you make sure all SELinux packages are updated.

libsepol, policycoreutils,selinux-policy and then reinstall docker-selinux
to see if the issues go away.

I'm also seeing this error in rawhide.  In addition, I can't update any selinux packages properly.  I was going to open a ticket for this, but it seems related to this, so I'll add it here.  I can open a new ticket if you prefer that.

  Upgrading   : selinux-policy-3.13.1-192.fc25.noarch                    23/931 
neverallow check failed at line 8863 of /var/lib/selinux/targeted/tmp/modules/100/base/cil
  (neverallow base_typeattr_12 unlabeled_t (file (entrypoint)))
    <root>
    allow at line 545 of /var/lib/selinux/targeted/tmp/modules/400/docker/cil
      (allow spc_t unlabeled_t (file (entrypoint)))
    <root>
    allow at line 828 of /var/lib/selinux/targeted/tmp/modules/100/sandboxX/cil
      (allow sandbox_x_domain exec_type (file (entrypoint)))
    <root>
    allow at line 1592 of /var/lib/selinux/targeted/tmp/modules/100/virt/cil
      (allow virtd_lxc_t exec_type (file (entrypoint)))
    <root>
    allow at line 1966 of /var/lib/selinux/targeted/tmp/modules/100/virt/cil
      (allow svirt_sandbox_domain exec_type (file (entrypoint)))

Failed to generate binary
semodule:  Failed!

  Upgrading   : pcre-8.39-0.1.RC1.fc25.x86_64                            13/931 
neverallow check failed at line 8863 of /var/lib/selinux/targeted/tmp/modules/100/base/cil
  (neverallow base_typeattr_12 unlabeled_t (file (entrypoint)))
    <root>
    allow at line 545 of /var/lib/selinux/targeted/tmp/modules/400/docker/cil
      (allow spc_t unlabeled_t (file (entrypoint)))
    <root>
    allow at line 828 of /var/lib/selinux/targeted/tmp/modules/100/sandboxX/cil
      (allow sandbox_x_domain exec_type (file (entrypoint)))
    <root>
    allow at line 1592 of /var/lib/selinux/targeted/tmp/modules/100/virt/cil
      (allow virtd_lxc_t exec_type (file (entrypoint)))
    <root>
    allow at line 1966 of /var/lib/selinux/targeted/tmp/modules/100/virt/cil
      (allow svirt_sandbox_domain exec_type (file (entrypoint)))

Failed to generate binary
semodule:  Failed!

  Upgrading   : selinux-policy-targeted-3.13.1-192.fc25.noarch          178/931 
neverallow check failed at line 8864 of /var/lib/selinux/targeted/tmp/modules/100/base/cil
  (neverallow base_typeattr_12 unlabeled_t (file (entrypoint)))
    <root>
    allow at line 545 of /var/lib/selinux/targeted/tmp/modules/400/docker/cil
      (allow spc_t unlabeled_t (file (entrypoint)))
    <root>
    allow at line 828 of /var/lib/selinux/targeted/tmp/modules/100/sandboxX/cil
      (allow sandbox_x_domain exec_type (file (entrypoint)))
    <root>
    allow at line 1592 of /var/lib/selinux/targeted/tmp/modules/100/virt/cil
      (allow virtd_lxc_t exec_type (file (entrypoint)))
    <root>
    allow at line 1966 of /var/lib/selinux/targeted/tmp/modules/100/virt/cil
      (allow svirt_sandbox_domain exec_type (file (entrypoint)))

Failed to generate binary
/usr/sbin/semodule:  Failed!

  Upgrading   : selinux-policy-minimum-3.13.1-192.fc25.noarch           374/931 
Failed to resolve 'data_home_t' in typeattributeset statement at line 472 of /var/lib/selinux/minimum/tmp/modules/100/xserver/cil
/usr/sbin/semodule:  Failed!

I just tried your suggested workaround.  When I tried to update the selinux packages, dnf said 'nothing to do'.

When I reinstalled docker-selinux, the error recurred.

stan, have you fully updated your system?

Yes.  When I run dnf, it tells me there is nothing to do.  However, it is skipping many packages (2804 at last count).  I'm trying to find out why, but because of the way dnf works, it is difficult.  See

https://bugzilla.redhat.com/show_bug.cgi?id=1340605

for more information about that.

Despite the errors above, it seems that selinux is updating.  I've thought of doing a relabel, though this computer was a fresh install of rawhide.  Do you think that would help?

No.  Relabel will not help.  

In the packages which will not install, is libsepol or policycoreutils in the list?

No, they are not.  The versions of them installed are:

libsepol-2.5-6.fc25.x86_64
policycoreutils-2.5-9.fc25.x86_64

And these are the latest versions available.

(In reply to stan from comment #7)
> No, they are not.  The versions of them installed are:
> 
> libsepol-2.5-6.fc25.x86_64
> policycoreutils-2.5-9.fc25.x86_64
> 
> And these are the latest versions available.

I have these very same packages and when I tried to update selinux-policy I got the same semodule errors as mentioned above.

When trying to reinstall docker-selinux, I'm getting:
$ sudo dnf reinstall docker-selinux
Last metadata expiration check: 2:03:16 ago on Tue May 31 07:14:49 2016.
Installed package docker-selinux-2:1.11.1-4.git9dea74f.fc25.i686 (from rawhide) not available.
Error: Nothing to do.

There was an update for selinux today, but no update for docker.  The errors were still there for selinux, with some additional errors for selinux-targeted.  I missed them on the original update, so picked them up with a reinstall.

  Reinstalling: selinux-policy-3.13.1-193.fc25.noarch                      1/10 
neverallow check failed at line 8867 of /var/lib/selinux/targeted/tmp/modules/100/base/cil
  (neverallow base_typeattr_12 unlabeled_t (file (entrypoint)))
    <root>
    allow at line 545 of /var/lib/selinux/targeted/tmp/modules/400/docker/cil
      (allow spc_t unlabeled_t (file (entrypoint)))
    <root>
    allow at line 828 of /var/lib/selinux/targeted/tmp/modules/100/sandboxX/cil
      (allow sandbox_x_domain exec_type (file (entrypoint)))
    <root>
    allow at line 1592 of /var/lib/selinux/targeted/tmp/modules/100/virt/cil
      (allow virtd_lxc_t exec_type (file (entrypoint)))
    <root>
    allow at line 1966 of /var/lib/selinux/targeted/tmp/modules/100/virt/cil
      (allow svirt_sandbox_domain exec_type (file (entrypoint)))

Failed to generate binary
semodule:  Failed!

  Reinstalling: selinux-policy-minimum-3.13.1-193.fc25.noarch              4/10 
Failed to resolve 'data_home_t' in typeattributeset statement at line 472 of /var/lib/selinux/minimum/tmp/modules/100/xserver/cil
/usr/sbin/semodule:  Failed!

  Reinstalling: selinux-policy-targeted-3.13.1-193.fc25.noarch             5/10 
  [44504.231641] SELinux:  Permission module_load in class system not defined in policy.
  [44504.232467] SELinux:  Class cap_userns not defined in policy.
  [44504.233274] SELinux:  Class cap2_userns not defined in policy.
  [44504.234059] SELinux: the above unknown classes and permissions will be allowed
neverallow check failed at line 8867 of /var/lib/selinux/targeted/tmp/modules/100/base/cil
  (neverallow base_typeattr_12 unlabeled_t (file (entrypoint)))
    <root>
    allow at line 545 of /var/lib/selinux/targeted/tmp/modules/400/docker/cil
      (allow spc_t unlabeled_t (file (entrypoint)))
    <root>
    allow at line 828 of /var/lib/selinux/targeted/tmp/modules/100/sandboxX/cil
      (allow sandbox_x_domain exec_type (file (entrypoint)))
    <root>
    allow at line 1592 of /var/lib/selinux/targeted/tmp/modules/100/virt/cil
      (allow virtd_lxc_t exec_type (file (entrypoint)))
    <root>
    allow at line 1966 of /var/lib/selinux/targeted/tmp/modules/100/virt/cil
      (allow svirt_sandbox_domain exec_type (file (entrypoint)))

Failed to generate binary
/usr/sbin/semodule:  Failed!

Ok I figured this out,  

You can edit /etc/selinux/semanage.conf and change expand-check to 0.

 When generating the final linked and expanded policy, by default
# expand-check check neverallow rules when executing all semanage
expand-check = 0

This should allow the policy to be installed.  I will look into why this is failing now.

https://github.com/fedora-selinux/selinux-policy/pull/127 

Should fix this in selinux-policy package.

Lukas can you get this merged.

The latest updates in rawhide seem to have fixed this.  I don't see any more errors from docker-selinux being updated.

This bug appears to have been reported against 'rawhide' during the Fedora 25 development cycle.
Changing version to '25'.

selinux-policy-3.13.1-208.fc25 has been pushed to the Fedora 25 testing repository. If problems still persist, please make note of it in this bug report.
See https://fedoraproject.org/wiki/QA:Updates_Testing for
instructions on how to install test updates.
You can provide feedback for this update here: https://bodhi.fedoraproject.org/updates/FEDORA-2016-662487f8f1

selinux-policy-3.13.1-208.fc25 has been pushed to the Fedora 25 stable repository. If problems still persist, please make note of it in this bug report.