Certas fontes (principalmente o PPA do Elementary Desktop) têm uma versão do network-manager-gnome que é mais nova que a do repositório canônico original. Uma correção foi emitida para o Natty, mas ainda não está no repositório do Maverick. Então, o Ubuntu vê a versão mais nova no elementary-desktop, usa isso em vez do canônico e, portanto, o bug.
A solução é reverter a versão do network-manager-gnome para o 0.8.1 + git.20100809t190028.290dc70-0ubuntu3 de 0.8.2 + git.20101123t161608.f143e76-0ubuntu1
Isso pode ser feito a partir do synaptic, procurando por network-manager-gnome e, em seguida, clicando em "force version" no menu package e selecionando a versão 0.8.1.