Eu também uso o Linux Mint 18 (Sarah). Cerca de alguns meses atrás, esse problema também começou a acontecer comigo (e ainda é problema no.1 com meu laptop).
Eu tentei encontrar a solução no Linux Mint help chanel cerca de 3 meses atrás. Caras me disseram que é provavelmente algum problema / bug com o indicador xfce. Então eles me aconselham a usar esses comandos para reiniciar o nm:
sudo service network-manager restart
que na verdade funciona , mas - nem todo tempo no meu caso. Às vezes, preciso sair e fazer login novamente (Ctrl + Alt + Backspace).
EDIT: Bem, depois de um tempo eu decido editar este post. Razão - eu encontrei um caminho! Finalmente, não preciso mais sair;
killall nm-applet; nohup nm-applet &
Funciona para mim, espero que seja útil para os outros.