My problem was that network-manager-openvpn-gnome was not installed, (weird because I though it would get installed automatically after installing network-manager-openvpn). I installed it and everything was fine.

So, to all people having the same problem make sure that

sudo apt-get install openvpn network-manager-openvpn network-manager-openvpn-gnome

after installing, restart the networking service, e.g. by executing

sudo /etc/init.d/networking restart