может что то с днс ?

#cat /etc/resolve.conf

попробуй по ip пингануть:
IP address of ya.ru is 213.180.204.8

или попробуй установить другую звонилку, например wvdial