Mira, yo hize una conexion por telefono con debian una vez y me acuerdo que me tomo mucho tiempo, ya que tenia que desactivarle unas opciones en /etc/ppp/options, en especifico la opcion que dice auth, comentala, a ver si a ti te funciona.