Can you create the problem on our demo site?

I don't believe such a problem exists. I recommend double check the user roles and maybe log out and in again to make sure the role cookie is up to date.

Note that you do not need to check any boxes, Content Administrator is a special system role, he already has edit and view permission without need to assign it to him.

Check also for script errors on your page or css problems that may hide the edit links.

When pages or content instances are marked with Admins only it is a special case, it locks down that content even from Content Administrators.

To change the permissions you can either login as a user in Administrators role and change them from the UI or you could do it from the database.

It should not redirect to access denied for a real user in administrators role, so I cannot explain that, it doesn't make sense to me since when a user is in the admins role we don't check what roles are allowed. 

If edit roles are blank then Admins and Content Admins roles can edit but no other roles can so you could fix it by the db with batch queries unless you need to preserve some other role permissions.