I use a VPS with multiple VMs (in proxmox) that run perfectly.
Do you just have internet access? Can you ping google? (DNS problem?)
I have tried the steps above and it works reasonably well, but then I run into the last problem. I don't want to immediately try something on my own as I might break more than I hope and then have to perform a reinstall. It's not the end of the world but rather not too often haha