Santiagozky, si tiens instalado el paquete PPP prueba a hacer desde consola como root:
#pppconfig
y dime que pasa.
Depende de la versión funcionará o no, si no funciona, dimeló y te mando un como que hize para Zonasiete, o mejor te digo donde esta:
www.zonalinux.org/ppp.html
el ppp en consola una vez configurado, funcionaría con los comandos pon y poff, es muy sencillo.
Dime lo que sea y si tu versión ppp es distinta, nos ponemos a ello.
El tema de Kppp está bien que funciona, pero es una faena tener que correr una cantidad ingente de librerias de kde si vas a trabajar en Gnome.
Otra cosa, cuando conectas con ppp aseguraté de no tener levantada ninguna red local, primero tendrías que tumbar la red, conectar ppp y levantar la red, para esto tengo un sencillo script que me hizo Ferdy, de manera que al arrancar el pc lo hace todo solo y se conecta.
Una vez que corras pppconfig, asegurate que tienes en /usr/bin/ los scripts pon y poff si no te los mete allí dimelo y te los paso.
Saludos