I ran a script to break inheritance and suddenly no domain users could get into the site.

The solution was to do an IISReset.

Another option is to check that the NT AUTHORITY\Authenticated Users have access to the site still.