Configure PolicyKit to allow non-local user to perform administration tasks that require authentication

On linux with policykit, if you try to use most GUI-based administration tools over a remote connection, they refuse to authenticate.

I believe this is an issue with policykit (for example, system-config-firewall fails with the error org.fedoraproject.slip.dbus.service.PolKit.NotAuthorizedException.org.fedoraproject.config.firewall.auth:)

However, the documentation for how to manage policykit rules is almost non-existant.

I've found a few bug-reports that seem related (here, here and here). However, they all seem to be slightly different, but related issues.

I'm a bit over my head here, and this is really a big deal for us, since the server I am working on is supposed to be run headless, and as it is, I cannot disconnect the monitor and properly administer it.

FYI, I'm using NX for remote admin, but it seems that the issue is present on NX, VNC, and tunneled X (ssh -X).

OS is CentOS 6.2.