Сами и ответили как бы. Чем-нибудь кроме спидтеста замеряли скорость (торрентами там или еще чем, что может выдать скорость скачивания == доступной скорости)?

А пинг проверяли тоже по картинкам спидтеста или $ ping host.com ?

было бы неплохо глянуть на traceroute до "проблемных" узлов. если никаких "звезд" не кажет и с маршрутизацией всё нормально, то копать в сторону ... в сторону того, что происходит с трафиком до шлюза, ну и на самом шлюзе. тут уже tcpdump в помощь

DNS-то тут при чем? Если траблы с прохождением пакетов, а не с резолвом хостов

А с клиентских машин до шлюза нормальный пинг?

Тогда смотреть чего там с пакетиками делает этот самый шлюз. Мб там шейпер накручен какой...

GLADIATOR13, ping, traceroute, netperf, iperf, pathrate, pathload, abget, iptraf
http://www.bog.pp.ru/work/network_performance.html
Выхлоп консоли показывай...

Думаю товарищи newzenon и Kettler правы.
Было бы неплохо посмотреть чего там творится в iptables (таблицы filter и nat). ip route list тоже было бы интересно глянуть (+ для всех таблиц, если пспользуется policy-based маршрутизация). И сеточку при этом можно немного описать - дабы понять что куда должно ходить. Если нет желания всего этого в паблик сливать - ставишь у себя на vpn-сервере iperf сервером, с клиентским машин смотришь его поведение. Потом точно-так же на любой машине в интернете (если будет нужно - в пм) и аналогичным образом с клиентов своих проверяешь. Если все ок - смотришь правила фаервола на limit по icmp и подобные вещи. Если после этих танцев с лебедями не удалось локализовать проблему - вооружаешься tcpdump'ом в двух консолях - в одной смотришь как пакетитки уходят с твоего интерфейса в сеть, в другой - как приходят к тебе на шлюз. Играешь в игру "найдите 10 отличий".
Но перед всеми этими шаманствами думаю стоит послушать товарища Kettler-а и проверить чего там с mtu происходит (т.е. уточнить у прова (или кто там этот vpn тебе предоставляет) его значение)