Boa tarde!
Não sei se será o caso, mas tive um problema "parecido" só que com conexões ethernet cabo mesmo ...
Faz o seguinte, vai num terminal e digita ifconfig ...
Procura saber qual o MTU que está configurado para a interface de rede... Tem que ser 1482... Pelo menos para mim, quando estava configurada por padrão como 1500, conectava, encontrava os sites.. mas ficava extremamente lento...
Se for o caso disto, acho que o comando para corrigir é ifconfig eth0 mtu=1492...
Da uma googlada para saber se é este o comando certo, se a configuração da MTU estiver em 1500 mesmo.
Não adiantou para mim, alterar pelo gerenciador das conexões de rede do Ubuntu... tive que fazer na unha msm...
Abraços