After upgrading to Ubuntu 15.10, the VPN started to behave very strangely. I use Private Internet Access and it worked just fine.
If I connect to a site that's blocked in my country right after I connect to a VPN - it works. However, after maybe 1 minute it's not working anymore: it shows the standard "this site is blocked" page. Interestingly, the ip-address remains the one provided by PIA (checked with Google) and http://whatismyipaddress.com shows the country I'm connecting through, not my country. The VPN connection icon is present and all seems to indicate the VPN works. Except that I can't access the site.
I tried connecting to VPN from my Android device and visiting the sites and it works all the time. So it clearly must be a newly introduced bug.
Update 1: it appears to be a DNS leak problem, looking for a solution how to solve it in Ubuntu.
Update 2: ended up writing PIA's DNS into /etc/resolv.conf manually, resolved my problem.