Поведение DNS во время соединения OpenVPN сразу улучшилось, когда я последовал предложению на ubuntuforums:
Откройте /etc/NetworkManager/NetworkManager.conf в редакторе с правами root. Удалите (или запишите с хешем #) строку, которая читает dns=dnsmasq Перезапустите NetworkManager через sudo service NetworkManager restart