Há um bug no Network Manager 0.9.4.0 que impede que ele detecte o modem 3G o tempo todo. Eu tive esse problema intermitente com o modem Huawei embutido no meu EeePC. O problema parece ter sido resolvido com o Network Manager 0.9.6.0, que vem com 12.10.
Você deve tentar reiniciar o Network Manager na primeira instância. Em um terminal:
sudo service network-manager restart
e veja se isso habilita o modem 3G quando você insere após a inicialização.
Considere a atualização para 12.10, a instalação do Network Manager 0.9.6.0 (em 12.04 LTS) ou aguarde até que o Network Manager 0.9.6.0 posterior seja atualizado em 12.04 LTS. Os upgrades de versão podem demorar um pouco para serem incorporados em versões anteriores, mesmo (ou especialmente) em LTS. Eu acredito que isso vai acontecer, mas provavelmente não será até este bug também é fixado para a satisfação de todos.
O 3G tem sido uma estrada difícil desde 11.04, receio. Como afirmado nesse bug, você terá que habilitar a banda larga sem fio novamente após cada inicialização ou retomada. Há uma boa alternativa que funciona para uma inicialização limpa.