Weird Internet issues after upgrading from UM 16.10 to 17.04

Support & Help Requests
,
#1

After upgrading, I can use HTTP, HTTPS, DNS, OpenVPN, and ICMP. No other protocols work. I can’t access email, Steam won’t update games, HITMAN won’t connect to servers, etc. I’ve tried unproxying my HTTP/S connection, changing my DNS server, and editing the files described in this post: Wifi issue in 17.04
But the only thing that helps at all is connecting to my VPN, which allows my to access Gmail, but nothing further.

EDIT:

I use Private Internet Access for my VPN. When I use the OpenVPN option, only Gmail begins working, but when I use their proprietary client, everything works as it should.

#2

Have you tried the workaround mentioned in https://ubuntu-mate.org/blog/ubuntu-mate-zesty-final-release/ ?

sudo apt install dnsmasq-base

#3

Yes, I did that right after I upgraded. It was already installed and at
version 2.76-5.