Parece que lembro de ter encontrado um problema semelhante há algum tempo. No meu caso, pelo menos, a causa raiz foi que a minha instalação do Ubuntu 9.10 estava faltando um monte de plugins do Network Manager. Procurando por plugins de gerenciadores de rede usando apt me forneça a seguinte lista (novamente em uma instalação 9.10):
% bl0ck_qu0te%Talvez valha a pena verificar se o plug-in que corresponde ao tipo de serviço VPN que você está tentando usar está instalado.