1) Se você tiver um dispositivo Android (de 2.2 ou 2.1), você pode habilitar o Wifi tethering e o Ubuntu reconhece-lo instantaneamente; então você insere a senha compartilhada e pronto; Se você quiser se conectar exclusivamente por bluetooth, então você deve dar uma olhada nestes dois guias oficiais:
Se você tem um iPhone, aqui está um programa que permite vincular-se a ele:
2) Quando você conecta um cabo de rede conectado a um roteador, o Ubuntu o reconhece sem problemas e você pode navegar na internet depois de menos de um segundo; então acho que isso deve ser um problema com seu roteador ou modem externo.