A sugestão comentada funciona. Instale o network-manager-openvpn-gnome e suas dependências. Se você não consegue se conectar à internet sem o vpn, você terá que obtê-los dos repositórios do Ubuntu através de outro computador. Comece aqui link Em seguida, selecione sua versão e procure o pacote pelo nome acima. Quando eu instalei no Lubuntu 12.10, foram necessários outros 4 pacotes. Certifique-se de baixar esses também e instale-os primeiro. Você pode instalar os arquivos .deb a partir de uma linha de comando usando (tentar executá-los de um gerenciador de arquivos também pode funcionar):
sudo deb -i packagefile.deb
Se você puder encontrar a ordem de dependência de todos esses pacotes, instale-os em uma ordem tal que nenhum pacote seja instalado antes de um pacote do qual dependa. Isso tornará as coisas muito mais simples.