Meu problema era que o network-manager-openvpn-gnome não estava instalado, (estranho porque pensei que seria instalado automaticamente após a instalação do network-manager-openvpn). Eu instalei e tudo estava bem.
Assim, para todas as pessoas com o mesmo problema, certifique-se de que
sudo apt-get install openvpn network-manager-openvpn network-manager-openvpn-gnome
após a instalação, reinicie o serviço de rede, por exemplo executando
sudo /etc/init.d/networking restart