I setup a VPN PPTP connection via network manager and it connects correctly (I see the lock near the notification icon and the message "Vpn connection has been successfully...")
As soon as I try to perform any SSH connection via the established tunnel the connection itself goes down with the message "Vpn connection failed".
the SSH connection always fails at
debug1: SSH2_MSG_KEXINIT sent
I've looked into the system logs and this is the log
Dec 12 12:25:00 ushuaia NetworkManager[1155]: <info> Starting VPN service 'pptp'...
Dec 12 12:25:00 ushuaia NetworkManager[1155]: <info> VPN service 'pptp' started (org.freedesktop.NetworkManager.pptp), PID 7093
Dec 12 12:25:00 ushuaia NetworkManager[1155]: <info> VPN service 'pptp' appeared; activating connections
Dec 12 12:25:00 ushuaia NetworkManager[1155]: <info> VPN plugin state changed: init (1)
Dec 12 12:25:00 ushuaia NetworkManager[1155]: <info> VPN plugin state changed: starting (3)
Dec 12 12:25:00 ushuaia NetworkManager[1155]: <info> VPN connection 'Redation' (Connect) reply received.
Dec 12 12:25:05 ushuaia NetworkManager[1155]: <info> VPN connection 'Redation' (IP4 Config Get) reply received from old-style plugin.
Dec 12 12:25:05 ushuaia NetworkManager[1155]: <info> VPN Gateway: 5.98.141.210
Dec 12 12:25:06 ushuaia NetworkManager[1155]: <info> VPN connection 'Redation' (IP Config Get) complete.
Dec 12 12:25:06 ushuaia NetworkManager[1155]: <info> VPN plugin state changed: started (4)
Dec 12 12:25:14 ushuaia NetworkManager[1155]: <info> VPN plugin state changed: stopping (5)
Dec 12 12:25:14 ushuaia NetworkManager[1155]: <info> VPN plugin state changed: stopped (6)
Dec 12 12:25:14 ushuaia NetworkManager[1155]: <info> VPN plugin state change reason: 0
Dec 12 12:25:15 ushuaia NetworkManager[1155]: <warn> error disconnecting VPN: Could not process the request because no VPN connection was active.
Dec 12 12:25:20 ushuaia NetworkManager[1155]: <info> VPN service 'pptp' disappeared
Please note that the same vpn is configured on my colleagues Windows 7 and works without problem when they use putty to connect via SSH
The most frequent cause of an issue like this is related to the router hardware and not your connection.
I have seen this problem before, when a Cisco router was used and configured to use a maximum MTU of 1500, and a VPN concentrator was used with a client MTU setting set to 1500. Your computer sends the vpn concentrator a packet of data that is 1500 bits, but the vpn tunnel it's self adds overhead (about 37 bits if memory serves) which makes the total size 1537 which can't make it through the router. This is a malformed packet and the router drops it.
The reason windows machines connect is because it ignores the concentrator's "suggestion" to set the packet size to 1500 and just uses what ever it wants.
Testing:
To make sure this is the problem, try sending a large file (about 1 meg) across the vpn without ssh. This will isolate any ssh issues from lower layer issues. If you get the same disconnect, it's probably the MTU issue.
The fix:
The proper fix is to have the network admin fix the vpn concentrator, setting a lower MTU then the router. Or perhaps fix the router...
From your side you can adjust the vpn MTU size down to say 1400 and everything will just work. There are several ways to do this but this page should give you a head start.