Network manager is one of the most buggy thing around. Everyone has problem with it. But if you try to use 'wicd', you will notice that it has more problems compared to network manager.

Yes you are not alone having this problem with it. There are many similiar posts on the internet. I remembered having this problem too but I can't remember what I did to fix it.

Part of network manager configuration is stored in /etc/NetworkManager, since your network connections are not working, I suggest you do this :-

$ sudo /etc/init.d/network-manager stop
$ sudo rm -rf /etc/NetworkManager/system-connections/*

After that reboot and then use the GUI to re-enter your configuration again. Hopefully it will recover from the deadlock.