@Necroscyth
So the server list appears ok when using the VPN ?
hotspotshield is ad supported as the free version, paid version doesn't have this
The free version is Ideal to test with, you are not meant to use the VPN in the long term but you can try using something like Adblock Plus possibly to block the ads.
The only way to confirm 100% this is a routing issue as indicated by the VPN making things work is to connect that PC to another ISP and see if all is good without the VPN.
Essentially somewhere between your ISP and the Server side is a broken internet path, normally these self resolve anywhere between minutes and weeks.