prova a cercare qualche stringa di inizializzazione del modem in rete

ad esempio prova
ATQ0 V1 E1 S0=0 X3 &C1 &D2 +MS=34

al posto di ATZ nelle opzioni di kppp o gnome-ppp


prova a mettere i dns del tuo provider in /etc/resolv.conf