I had the same issue, luckily I was able to figure out a fix. There appears to be an issue with the latest update of Network Manager. If you open the Ubuntu Software Center, go to History, search the keyword "Network" and you will probably see "network-manager (0.9.4.0-0ubuntu4, 0.9.4.0-0ubuntu4.1)".
If you see this then you have the same problem as I did. The solution is to downgrade to version 3: Search in Google "ubuntu network-manager package" and select the ubuntu.com link, then scroll down the page to "network-manager-dbg" select the precise (debug) ubuntu3 version.
Download the 4 related packages for your system (amd64 or i386):
network-manager (= 0.9.4.0-0ubuntu3)
network management framework (daemon and userspace tools)
libnm-util2 (= 0.9.4.0-0ubuntu3)
network management framework (shared library)
libnm-glib4 (= 0.9.4.0-0ubuntu3)
network management framework (GLib shared library)
libnm-glib-vpn1 (= 0.9.4.0-0ubuntu3)
network management framework (GLib VPN shared library)
Install each of them using the command sudo dpkg -i FILENAME.
Restart your computer and that should fix your problem!