Isso acontece comigo também (exceto com o OpenVPN), e para consertar usei o sudo killall dnsmasq. Infelizmente eu tenho que fazer isso toda vez que eu desligar e reconectar a minha VPN, mas é melhor do que nada!
EDIT: Eu encontrei uma solução. Vá para o terminal e digite
gksudo gedit /etc/NetworkManager/NetworkManager.conf
E comente a linha dns = dnsmasq
Aqui está o link para onde encontrei esta informação link