Abra o terminal e passe o comando:

sudo pppoeconf

Siga o passo-a-passo e ao final marque a opção conectar no boot para que a interface seja levantada logo que se inicia seu Linux.

Se tiver dificuldades, escolha as seguintes opções quando surgirem as janelas no passo-a-passo, responda da seguinte forma: Sim, Sim, Seu nome de usuário, Sua senha, Sim, Sim.

Caso no próximo boot a conexão não seja estabelecida, use os seguintes comandos em um terminal.

Para conectar:

pon dsl-provider

Para desconectar:

poff -a

Para mostrar status:

plog

Esta dica funciona em qualquer distribuição, é isto aí, continuem usando Linux!

Fonte (com screenshots): http://carlrobers.wordpress.com/2009/11/18/ubuntu-9-10-conectar-a-internet-com-o-velox-modo-terminal/