@User One thing that has been on my mind is the TAP and TUN interfaces that a VPN provider would create. Perhaps ubuntu is trying to connect to the internet using those interfaces so removing them might fix it? Its a shot in the dark but maybe you might be able to find something on Google around those queries.