Eu tenho tethering para trabalhar em uma distribuição Linux diferente, mas acredito que o mesmo método que usei se aplicará ao Ubuntu, porque tudo é feito através da linha de comando.
Primeiro, instale o macchanger. Deve estar nos seus repositórios. Ele permite que você altere o endereço MAC de uma interface. Eu descobri que meu problema estava vindo do telefone dando um endereço MAC de 00: 00: 00: 00: 00: 00 quando o tethering estava habilitado e o computador não podia trabalhar com isso. Depois de instalar o macchanger, digite os seguintes comandos, substituindo a eth1 pelo que seu computador chama a interface do telefone:
macchanger -r eth1
ifconfig eth1 up
dhclient eth1
Você pode precisar usar o sudo para os comandos funcionarem. Se você não tiver dhclient no seu computador, digitar dhcpcd eth1
deve funcionar.
Agora você deve conseguir acessar a Internet por meio da conexão vinculada. Você terá que fazer essas etapas toda vez que quiser se conectar.