Aqui está um link do bug .
E aqui está o que você deve tentar:
Abra um terminal e digite ou cole isso e execute-o:
sudo -H gedit /etc/NetworkManager/NetworkManager.conf
Em seguida, edite o arquivo e adicione essas linhas à parte inferior do arquivo:
[device]
wifi.scan-rand-mac-address=no
Salve o arquivo e execute este comando em um terminal:
sudo service network-manager restart
EDITAR: Desculpe, apenas leia sua edição para sua pergunta.
Experimente esta linha de código (consertou minha internet em 16.10 e 17.04:
sudo killall dnsmasq