gnome-ppp o gkdial dovresti trovarli

puoi anche usare kppp da gnome tranquillamente

per la connessione
guarda il file /etc/ppp/options se ha una riga con scritto solo


auth
se la vedi commentala

#auth

e riprova