How can I troubleshoot "VPN Connection Failed"?

Is there anyway to get an error log for a failed VPN connection attempt? All I get is this notification and I have no idea where to go from there.

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.

What kind of VPN are you trying to establish?

Is it PPTP (Microsoft proprietary) or Cisco-compatible ?

The easiest way would be for you to run pptp (for PPTP) or vpnc (for Cisco) from a console and see the possible errors interactively.

I think that vpnc is quite straight forward, you just need to type in the necessary info (gateway ip, group name/pass, user name/pass).

I haven't actually used a PPTP VPN, but some info about setting it up can be found here at cyberciti