Acabei de ter o mesmo problema que corrigi. Eu estava tentando adicionar uma conexão OpenVPN (você não afirmou qual tipo de VPN você está usando), mas a idéia vai funcionar. Eu já tinha openvpn e network-manager-openvpn instalado via apt, mas precisava adicionar network-manager-openvpn-gnome
sudo apt install network-manager-openvpn-gnome
em seguida, reinicia o gerenciador de rede (isso mata a rede até que seja totalmente reiniciado)
sudo service network-manager restart
Depois disso, eu poderia abrir as configurações do sistema novamente, ir para a rede e adicionar minhas coisas sobre o OpenVPN.
Isso tem sido um problema há alguns anos e foi respondido aqui: Não é possível carregar o editor de conexão VPN no Ubuntu 14.04 LTS
Felicidades