Sim, é possível. Eu tenho Ubuntu 11,04, NetworkManager 0,8,4, telefone Android Nexus One rodando Cyanogenmod 7.
Como descrito por Roman, clique com o botão direito do mouse no ícone do NetworkManager e escolha "Criar nova rede sem fio". Eu escolhi deixar a conexão aberta (sem WPA, sem WEP). Meu telefone conseguiu ver a rede imediatamente e eu me conectei sem problemas. A ponte foi feita automaticamente para que eu pudesse navegar na internet sem configurar nada extra.
O motivo pelo qual você está tendo problemas com o método acima é porque o Android 2.3 não suporta redes ad-hoc. Para ser preciso, o wpa_supplicant do Android não mostra redes ad-hoc. Existem várias maneiras de corrigir isso. Procure o Google e vá caçar nos fóruns xda-developers. Você provavelmente precisará fazer alguns hackers no seu telefone que estão além do escopo desta resposta.
Minha recomendação pessoal: se o seu telefone for compatível com o Cyanogenmod, você poderá instalá-lo para obter suporte ad-hoc e outras delícias extravagantes. Você precisará enraizar seu telefone, o que pode ou não ser do seu gosto.
Outra alternativa é tentar "modo de infra-estrutura". Depois de configurar a rede sem fio ad-hoc conforme acima, clique no ícone do NetworkManager, escolha "Editar conexões". Bata na guia sem fio e edite a rede ad-hoc que você acabou de criar. Em Modo, escolha "Infraestrutura". Não tenho certeza se isso funcionará para você, já que não tenho um telefone Android padrão para testar. Meu pensamento é se o modo ad-hoc é o problema, então o outro modo pode ser a solução.
Boa sorte!