Eu tive esse mesmo problema de não conseguir navegar apesar de estar conectado, então pesquisando na Web e lendo bastante este forum durante mais ou menos 6 dias, resolvi fazer o seguinte, hoje dia 15/10/2010.
1- desinstalei o (ifupdown) pelo Synaptic, consegui navegar, mas a cada boot tinha que usar o pppoeconf
2- instalei de novo o ifupdown, mais o pacote pppoe, e o pacote resovlcon
3- ao dar o boot esta logando normalmente e a Internet entra automaticamente
leiam neste link o que falam sobre esse bug das versões 9.04 e 9.10
http://ubuntuforum-pt.org/index.php?topic=58362.0No Gerenciador de redes esta marcado rede com fio, ifupdown (eth0) usada (nunca) não tendo nenhuma outra configuração DSL ativada.
Espero ter ajudado, meu modem é o antigo SpeedStream 5200, mas não sei dizer se ele é roteado ou não.