Failed to add/activate connection. (32) Insufficient privileges

I am doing a fresh install of a minimal Ubuntu system with MATE desktop environment. When I click on NetworkManager's icon and then a wireless network to connect to, I receive a dialog box that says:

Connection failure

Failed to add/activate connection

(32) Insufficient privileges.

I am doing a clean reinstallation of Ubuntu 14.04 with Lubuntu 14.04.1 alternate installer and choose F4 -> "Install a basic command-line system", then install X, MATE and NetworkManager manually like this:

sudo apt-get install software-properties-common -y
sudo apt-add-repository ppa:ubuntu-mate-dev/ppa -y
sudo apt-add-repository ppa:ubuntu-mate-dev/trusty-mate -y
sudo apt-get install xorg mate-core --no-install-recommends -y
sudo apt-get install network-manager network-manager-gnome --no-install-recommends -y

If that helps, when I install Ubuntu that way, it asks for password upon attaching and unmounting a USB flash drive. Also, when I am creating a shortcut for shutdown command, to be able to shut down my computer with a click on an icon, I have to alter permissions for /sbin/shutdown:

chmod u+s /sbin/shutdown

Maybe something similar is going on with Wi-Fi and I need to alter some permissions for it to work properly?

Step 1

This can be cured by fixing PolicyKit rule for the NetworkManager. First of all check whether .pkla file with [nm-applet] section already exists in /etc/polkit-1/localauthority/10-vendor.d. If yes, make a backup of it and alter ResultAny=no value to yes in [nm-applet] section of this file.

The structure of these policy rule files is described here.

If this file is absent in 10-vendor.d folder, we will create PolicyKit rule manually. Create the file with the name org.freedesktop.NetworkManager.pkla containing the next lines:

[nm-applet]
Identity=unix-user:your_username
Action=org.freedesktop.NetworkManager.*
ResultAny=yes
ResultInactive=no
ResultActive=yes

Replace your_username in this file with your real login name. If you wish to add several users, change the Identity entry like this (and replace usernames with the desired ones):

Identity=unix-user:username1;unix-user:username2

If you wish to add even more users, then you should consider adding all of them to netdev group with useradd and change the rule to:

Identity=unix-group:netdev

Now copy this .pkla file to the PolicyKit directory:

sudo cp org.freedesktop.NetworkManager.pkla /etc/polkit-1/localauthority/50-local.d/

Step 2

You should also check whether PolicyKit Authentication Agent is running - this rule won't work without it. If ps -ef | grep kit | grep agent returns nothing, then it isn't running.
Check whether this binary exists. For GNOME this file can be found here:

/usr/lib/policykit-1-gnome/polkit-gnome-authentication-agent-1

For MATE it is located here (for 32-bit and 64-bit respectively):

/usr/lib/i386-linux-gnu/polkit-mate/polkit-mate-authentication-agent-1
/usr/lib/x86_64-linux-gnu/polkit-mate/polkit-mate-authentication-agent-1

Its location may vary in different DE. If it was not found there, seek for it:

locate agent | grep -v -E '^/var|doc|so|helper' | grep pol

If you found nothing, then PolicyKit Agent isn't installed at all. Search for the package name in APT database with apt-cache search PolicyKit Authentication Agent command and install appropriate package for your DE. For MATE it will be mate-polkit.

It doesn't start automatically for some reason. You can search /etc/xdg/autostart for the PolKit Agent .desktop launcher and analyze why it fails to start. Or you can create your own launcher using "Startup Applications" of your DE and add the Polkit Authentication Agent command to start it properly.

If you are interested, there's an extensive and nice article about PolicyKit privileges.