Nevermind guys, I think I have found the solution. It looks like the fact that the two VPN programs refused to work was a coincidence but I managed to solve both. For Fruho you shouldn't use the .deb file from their website but install it as follows:
wget -O fruho.deb https://github.com/fruho/fruhoapp/releases/download/fruho-0.0.21/fruho_0.0.21_amd64.deb
sudo dpkg -i fruho.deb
sudo apt-get install -f
Alternatively, for 32-bit computers replace the first line with:
wget -O fruho.deb https://github.com/fruho/fruhoapp/releases/download/fruho-0.0.21/fruho_0.0.21_i386.deb