ubuntu, dns, vpn
It'll technically be a downgrade (it'll say as much in the console) but when it's done, and a reboot has occurred, DNS will work as expected on your VPN connection.
Full commands because of character limits:
apt install --reinstall network-manager=1.10.6-2ubuntu1.1
apt install --reinstall network-manager-config-connectivity-ubuntu=1.10.6-2ubuntu1.1
ubuntu, dns, vpn
There are a few other packages that also appear to be related (and which I "updated" the same way):
gir1.2-nm-1.0=1.10.6-2ubuntu1.1
libnm-glib-vpn1=1.10.6-2ubuntu1.1
libnm-glib4=1.10.6-2ubuntu1.1
libnm-util2=1.10.6-2ubuntu1.1
libnm0=1.10.6-2ubuntu1.1
Although I must admit that everything started working for me after just downgrading network-manager. The other packages I only downgraded "just in case".