I take it you're using NetworkManager to connect ?
NetworkManager uses different plug-ins for different types of VPN connections (such as network-manager-openvpn), what type of connection is it, and have you tried reinstalling the plug-in ?
When you deleted the connection, and recreated it .. did you try giving it a different Connection Name: ?
Have you trawled through your log files for relevant information ?