Some vpn do not uninstall correctly especially the free or very cheap ones. The new vpn should be able to install and fix this but if it does not work for you it is hard to recommend a fix. There are so many variations of these vpn clients.
The machine I had this issue ended up with the brute force reinstall windows to fix it. This is why I always run vpn on my router. There is no client to install.