Acabei de ter exatamente o mesmo comportamento - adicionar os usuários à lista de autoridades permite que eles acessem, mas não o grupo.
No meu caso, tive que reinstalar o pacote libpolkit-gobject-1-0
, que de alguma forma removi acidentalmente.
Parece que o policykit precisa dessa biblioteca para descobrir em quais grupos um usuário está.