Summary: Permissions changes were not saving.
Solution: On localhost, upping max_input_vars solved the problem. For shared hosting, the Filter Permissions module.
After migrating our new site to our shared host in Japan, I noticed that some permissions were not correctly set. However, no changes I made to permissions were saving. Our hosting service also limits max_input_vars to 1000, which did not seem high enough.
The Filter Permissions module resolved this for me and as an extra benefit, the unwieldy mess that was my permissions page is a lot more manageable.
Solution found here on Drupal.org.