Digite isto no seu terminal: ping www.google.com
Quando você pressionar Enter, ele começará a fazer ping no Google e um longo fluxo de texto ficará visível no terminal. Se depois de pressionar enter, esta mensagem será exibida "Host not found". Então talvez o seu driver WiFi não seja compatível com o Ubuntu 16.04. Mude para 14.04 ou execute 16.04 usando um USB ativo e tente conectar-se e navegar na Internet. Se ele se conectar e a Internet funcionar bem no Live USB, reinstale o Ubuntu.
Eu também enfrentei esse problema, mas quando inicializei usando o Live USB, o problema foi resolvido.
Deixe-me saber se isso funciona. :)