Comment 4 for bug 514775

http://osdir.com/ml/debian-bugs-dist/2010-01/msg07864.html

That bug seems to describe this one perfectly. The second solution presented worked for me on lucid with one caveat:

service network-manager stop
rm /var/lib/NetworkManager/NetworkManager.state
service network-manager start

At this point knetworkmanager still did not work properly, I restarted the computer and it worked. Restarting the session, ie: logging out and back in, probably would have worked also but I did not try this.