Eu estava com esse mesmo problema, lendo varios artigos um deles aconselhava a instalar no Synaptic os pacotes, pppoe, resolvcon e reinstalar o pacote pppoeconf. Assim fiz e minha conexão sempre que ligo o computador ela esta ativa e nunca mais sumiu, apesar de na barra de ferramentas o ícone do network-manager ter sumido mas não me interessa ele, pois sei que estou conectado pela informação meteorológica da minha cidade Rio de Janeiro, mostrando a temperatura.
Uso o Ubuntu 10.4.1 LTS, Velox, modem Speedstream 5200, com 5 anos de uso.