I had the problem with Ubuntu 16.04 out-of-the-box. After a full week of 12 hour days trying to resolve this issue, I was finally about to fix it. I made a longer post about it here:
Here's the abbreviated version.
Step 1: Goto GitHub and clone the following repo to your home folder:
Step 2: Move the .sh files from your cloned rep to the /etc/openvpn folder:
sudo chmod +x *.sh && sudo mv *.sh /etc/openvpn
Step 3: Run the following command to install new packages for DNS:
sudo apt-get install openresolv nscd unbound
Step 4: Append the following line to your OpenVPN Client Configuration files (*.ovpn or *.conf). I did this after the configuration directives but before my inline certs (
up "/etc/openvpn/update-resolv-conf.sh /etc/openvpn/update-systemd-network.sh"
down "/etc/openvpn/update-resolv-conf.sh /etc/openvpn/update-systemd-network.sh"
This should resolve the DNS resolution problem. Dmitry has the right steps, but I needed the 2nd script for my system to update. Works like my 14.04 system... before I upgraded to 16.04...