O applet que gerencia esse ícone é chamado nm-applet .
No meu caso, eu tinha uma entrada de início automático para ele em ~/.config/autostart/nm-applet.desktop , que eu havia criado no Ubuntu MATE 14.10. (Se você não fizer isso, copie nm-applet.desktop de /etc/xdg/autostart/ .)
Depois de comentar as duas linhas a seguir:
#AutostartCondition=GNOME3 unless-session gnome
#Hidden=true
e saindo e voltando, o applet estava lá novamente.
Observação: se você usar outros ambientes de desktop além do MATE, talvez seja necessário reativar o AutostartCondition e ajustá-lo de acordo com as suas necessidades.
Nota 2: isto já não parece funcionar em 18.04.