Nunca tive um problema com isso. Eu simplesmente habilitava o tethering via USB nas configurações dos meus telefones, e o Ubuntu se conectava facilmente. Você pode confirmar que você ativou o tethering de USB? Para ligar via Wi-Fi, ative o tethering WiFi nas configurações do telefone, procure o ssid em conexões sem fio no Ubuntu e conecte-se como de costume. Você também pode tentar amarrar via Bluetooth, mas será lento.