A pasta /usr/share/applications pertence ao root, então você não poderia apagar nada de lá (a menos que vc estivesse em uma sessão de root, o que é totalmente contra-recomendado). O atalho ainda deve estar na pasta, só deve ter saído da sua área de trabalho.
Dê uma olhada na lixeira do seu desktop, pra ver se a cópia do atalho não foi pra lá.
Obrigado zekkerj por responder.
Uma vez ou outra temos que mexer nestas pastas para deixar o ubuntu do nosso gosto, mas obrigado pelo aviso. Consegui sanar reinstalando o Network-manager-gnome, assim ele voltou pro menu. Obrigado.
