Não está vendo o gerenciador de VPN que você instalou. Depois de instalar um que seja suportado, como o openvpn, o botão Adicionar será ativado.
Acabei de trocar para o Debian do Ubuntu e não consigo descobrir como adicionar uma conexão VPN através do gerenciador de rede. Quando seleciono a guia VPN em Editar Conexões, o botão Adicionar fica desativado.
Estou executando uma nova instalação do Debian 6.0.1 Já instalo o cliente VPN da Cisco (network-manager-vpnc).
Qualquer ponteiro seria ótimo.
Você precisa instalar o gerenciador de rede:
sudo aptitude install network-manager-vpnc
Além do cliente gnome:
sudo aptitude install network-manager-vpnc-gnome
Em @Sileria answer, você também precisa instalar o gerenciador de rede e o cliente gnome para o tipo de conexão PPTP:
sudo aptitude install network-manager-pptp network-manager-pptp-gnome
Tags vpn vpnc debian networkmanager