Could you attempt to do the following.
First to see if ubuntu software center has really removed network-manager, as follows:
dpkg -l | grep network
check for something like this:
ii network-manager 0.8~a~git.20091013t193206.679d548-0ubuntu1 network management framework daemon
ii network-manager-gnome 0.8~a~git.20091014t134532.4033e62-0ubuntu1 network management framework (GNOME frontend
If it's there, try removing it as follows:
sudo dpkg -r network-manager
Then check with the first shell command if it's gone.