The fact that people are able to connect while using a VPN all but confirms it: Square-Enix are to blame, via throttling / restricting access to FFXIV from certain IP address ranges.
If you are in the UK, or another country which allows for easy IP address renewal, try the following:
1. Find your IP address by clicking here:
https://www.google.co.uk/#q=what+is+my+ip
2. Note it down, then power off your router for about 1 minute, then back on.
3. Check the link again. If your IP address range has changed (e.g. from 46.208.xxx.xxx to 87.103.xxx.xxx), then try FFXIV again. If not, reset your router again (perhaps for a little longer if your IP didn't change at all).
The idea behind this is that, being in the UK, we sometimes get assigned IP addresses that make it look like we're in different countries (e.g. the Netherlands). If Square-Enix is restricting via IP address range, then a change of IP to an "acceptable" range might resolve the issue.
Let me know if anyone tries these steps with any success.