O problema não no Ubuntu, enfrentei o mesmo problema no Windows 7
De alguma forma, o PC não reconhece a rede do Android com o DNS. Para resolver esse problema, você está usando algum aplicativo de conexão de bloqueio no seu android?
Se sim desativá-lo, tente usar o tethering de USB, se o mesmo problema fizer o seguinte:
- Instalar (Configurar DNS ou DNS Changer) no Google play
-
Definir o DNS do Google
DNS1: 8.8.8.8
DNS2: 8.8.4.4
Em seguida, pressione conectar, depois tente ativar o tethering USB.
Deve funcionar