Eu também tenho o mesmo problema desde a atualização para a versão 16.04 do LTS. Quanto a onde vem, eu não poderia comentar, mas não me lembro de ser um problema com 14.04
Você pode colocar o gerenciador de rede em funcionamento novamente, sem reinicializar, acessando o terminal Ctrl + Alt + t e digitando o seguinte comandos:
sudo ifconfig eth0 up
sudo dhclient eth0
então:
exit
para fechar a tela do terminal.
Não é uma solução ou uma correção permanente, mas um trabalho digno que não requer uma reinicialização que pode ser inconveniente.