Descobrimos que o compartilhamento de conexão precisa estar ativado no telefone. Eu instalei um aplicativo no telefone que compartilha a conexão (para o N900, ele é chamado de bluetooth-dun) e no novo emparelhamento, o Ubuntu automaticamente se ofereceu para usar a conexão de Internet do telefone. Eu acho que devo ter visto a opção ao emparelhar com o telefone de outra pessoa antes.
Então ele mostrou um assistente para a configuração (escolhendo um provedor e um plano) e depois que eu o preenchi, funcionou. Pelo menos é assim que funciona no 11.04.