Connect to WiFi does not work first time

Steps to reproduce:

1) Delete any reference to your WiFi connection in "Edit Connections" and disconnect.
2) Find it in the WiFi list (from the applet) and click it.
3) Type your WiFi password and hit enter.
4) The password window goes away but no WiFi connection is established.
5) Open "Edit Connections" and observe that the WiFi password is blank.
6) Try again and it usually works.

I would expect it to connect first time and for the password to be stored and showing in "Edit Connections".

This has been tried with a fresh 16.04 install both without any updates and with all latest updates.

ProblemType: Bug
DistroRelease: Ubuntu 16.04
Package: network-manager-gnome 1.2.0-0ubuntu0.16.04.1
ProcVersionSignature: Ubuntu 4.4.0-22.40-generic 4.4.8
Uname: Linux 4.4.0-22-generic x86_64
ApportVersion: 2.20.1-0ubuntu2.1
Architecture: amd64
CurrentDesktop: Unity
Date: Fri Jun 3 12:25:54 2016
ExecutablePath: /usr/bin/nm-applet
IfupdownConfig:
 # interfaces(5) file used by ifup(8) and ifdown(8)
 auto lo
 iface lo inet loopback
InstallationDate: Installed on 2016-06-03 (0 days ago)
InstallationMedia: Ubuntu 16.04 LTS "Xenial Xerus" - Release amd64 (20160420.1)
IpRoute:
 default via 192.168.43.1 dev wlp1s0 proto static metric 600
 169.254.0.0/16 dev wlp1s0 scope link metric 1000
 192.168.43.0/24 dev wlp1s0 proto kernel scope link src 192.168.43.218 metric 600
NetworkManager.state:
 [main]
 NetworkingEnabled=true
 WirelessEnabled=true
 WWANEnabled=true
ProcEnviron:
 LANGUAGE=en_GB:en
 PATH=(custom, no user)
 XDG_RUNTIME_DIR=<set>
 LANG=en_GB.UTF-8
 SHELL=/bin/bash
RfKill:
 0: phy0: Wireless LAN
  Soft blocked: no
  Hard blocked: no
SourcePackage: network-manager-applet
UpgradeStatus: No upgrade log present (probably fresh install)
nmcli-dev:
 DEVICE TYPE STATE DBUS-PATH CONNECTION CON-UUID CON-PATH
 wlp1s0 wifi connected /org/freedesktop/NetworkManager/Devices/0 HTC Portable Hotspot DF99 1fa9f4e3-6435-4c48-a834-e75c51ddd146 /org/freedesktop/NetworkManager/ActiveConnection/9
 lo loopback unmanaged /org/freedesktop/NetworkManager/Devices/1 -- -- --
nmcli-nm: Error: command ['nmcli', '-f', 'all', 'nm'] failed with exit code 2: Error: Object 'nm' is unknown, try 'nmcli help'.