How can I troubleshoot "VPN Connection Failed"?

Log is written to /var/log/syslog.
Open gnome-terminal and do sudo tail -f /var/log/syslog
This will follow the file (prints to terminal new log messages).
Now try to connect to the vpn, the messages then will start showing in the terminal.
When you are done following the log just click Ctrl+c to quit tail.

One can add markers to the log by opening another terminal and doing something like that:
logger "............... Starting VPN... "

The new (systemd-)variant to get the logs is

journalctl -u NetworkManager.service

In Fedora and other systemd distro's that do not have /var/log/syslog, the VPN logs can be accessed with "sudo journalctl -f"

-f is for follow.