Você está executando a versão 14/04 (Trusty) do Ubuntu? Eu estava passando por um problema semelhante quando atualizei meu laptop para 14.04. Meu modem de banda larga AT & T / Sierra 313, que funcionava sob todas as versões anteriores do Ubuntu, não funcionaria mais e a opção de banda larga móvel também não funcionaria
Eu determinei que o problema parece estar com a nova versão do pacote "Modem manager" instalado com o 14.04. Consegui consertar o problema fazendo o downgrade de apenas um pacote para a versão de 12.04 (Precise), pois esta versão ainda é suportada e está disponível. Os passos que dei estão documentados na resposta que publiquei para a minha própria pergunta, aqui:
O modem de banda larga 3G Wireless Sierra 313u não funcionará desde a atualização para o 14.04