Apparently you need to have the network-manager-openvpn-gnome package installed in order for VPN to work:
Most notably, Kubuntu lacks a necessary package that allows the Network Manager to detect the available encryption ciphers. Without those, the VPN service cannot negotiate with the remote side and established a secure tunnel. In the Advanced settings, under Security, you will see a naughty and unnecessary error that reads OpenVPN cipher lookup failed. Not nice.
I had to install the deceptively named network-manager-openvpn-gnome package and restart the network service before I could complete the VPN configuration. I wonder why Kubuntu would not have this package installed in the first place. I also had to setup LZO compression to get things moving.
We should consider installing the network-manager-openvpn-gnome package by default.