Eu encontrei o sucesso com a seguinte solução no Ubuntu 13.04:
Abra /usr/share/polkit-1/actions/org.freedesktop.NetworkManager.policy
com privilégios root / sudo e pesquise a seguinte linha:
<message>System policy prevents modification of network settings for all users</message>
Algumas linhas abaixo disso devem ser:
<allow_active>auth_admin_keep</allow_active>
Altere para:
<allow_active>yes</allow_active>
Salve o arquivo e reinicie o computador.