Hast du mal die VPN-Plugins inkl. dem gesamten NetworkManager reinstalliert?
sudo apt-get install network-manager-openvpn network-manager-openvpn-gnome network-manager-pptp network-manager-pptp-gnome network-manager-vpnc network-manager-vpnc-gnome network-manager-openconnect network-manager-openconnect-gnome network-manager network-manager-gnome