Maybe they just blocked access to their DNS (or even to any other DNS), and having the VPN connection you could connect with no problems to other DNS and then to wherever else in the internet because other ports were not blocked?
Can you do some nmap scan to detect which communication is blocked?