I encountered this problem today after running an distribution update, upgrading from 12.04 (Precise) to 12.10 (Quantal).
NetworkManager appeared to connect ok – I had an been assigned an IP address from the router etc, but still had no internet connectivity.
Running the following command fixed the problem:
sudo dpkg-reconfigure resolvconf
It is a known bug and is documented here: https://bugs.launchpad.net/ubuntu/+source/network-manager/+bug/1051348