I have a similar problem. I tried rolling back the network manager from 1.2.6-0ubuntu0.16.04.1 to 1.2.2-0ubuntu0.16.04.4. Oddly, it seemed to fix DNS for a few minutes, but it reverted to not working.
I noticed that a few days before the network manager was updated resolvconf also updated. I believe resolvconf is responsible for notifying applications (like the local resolver) when something like a DHCP lease gets established and a new DNS server is needs to be pointed to.
I downgraded resolvconf from 1.78ubuntu4 to 1.78ubuntu2 and this seems to have fixed my problem.
I have a similar problem. I tried rolling back the network manager from 1.2.6-0ubuntu0. 16.04.1 to 1.2.2-0ubuntu0. 16.04.4. Oddly, it seemed to fix DNS for a few minutes, but it reverted to not working.
I noticed that a few days before the network manager was updated resolvconf also updated. I believe resolvconf is responsible for notifying applications (like the local resolver) when something like a DHCP lease gets established and a new DNS server is needs to be pointed to.
I downgraded resolvconf from 1.78ubuntu4 to 1.78ubuntu2 and this seems to have fixed my problem.