muita gente reclama, ja experimentou utilizar o opendns?
suas dns são:
208.67.222.222
208.67.220.220
após conectado pelo gnome ppp, tente deixar o arquivo /etc/ppp/resolv.conf apenas com essas dns e verifique se melhora.
não sei se o gnome ppp utiliza o /etc/ppp/resolv.conf ou o /etc/resolv.conf, então, teste ambos com essas dns.