Что за интернет хоть? Тип подключения? Возможно проблема в DNS (у меня было подобное).
Покажите на всякий случай вывод:
cat /etc/resolv.conf
P.S. У меня была проблема в Debian. После настройки VPN поднимался и работал, но сайты грузились медленно. Как оказалось проблема была в DNS - шлюз подставлялся на 1-е место в resolv.cof а нужно было, чтобы первым был DNS IP-адрес провайдера.