você tem os compiladores instalados no seu sistema (make, gcc, build-essential, linux-headers-2.6.15-generic e etc)?
Abre um terminal e digita:
ls -l .wvdial.conf
cola aqui o resultado.
e também:
ls -l /usr/sbin/pppd
OBS: Após instalar o pacote .deb e fazer as alterações que falei, reinicie seu sistema e só então tente usar o gnome-ppp por que o script que se encarrega de ativá-lo só vai ser executado no boot.