Comment 16 for bug 964705

The link posted by piviul contains a fix, though it requires every user to be in the adm group. My preferred fix is actually slightly different and just requires the person to be logged in. The following policy is applied on all mobile computers that I manage:

/etc/polkit-1/localauthority/30-site.d/10-users-edit-connections.pkla

[Allow all users to create network connections]
Identity=unix-user:*
Action=org.freedesktop.NetworkManager.settings.modify.system
ResultAny=auth_self
ResultInactive=no
ResultActive=yes

In case any ubuntu developers are reading this: It is annoying that the default policy forbids users to add or change network conections, as I think the security benefits are marginal. The current default policy is only correct on Ubuntu-based server's. I think it might be a better solution to have a more open default policy, but have a "server-security-policy" deb which gets installed by default with the ubuntu-server installs, and is available in the repos. This server-security-policy package/metapackage would pull in polkit policies that forbit users from editing connections. Obviously this leaves the door open to an even greater variation in security policy between desktops and servers as the need arises.