So since 20.04 was working fine for me, I ended up installing Ubuntu 20.04 LTS on the server and then manually upgrade it to 22.04 after which I tried installing VirtualMin on it again and everything works beautifully now.
I’ll drop the server provider a message and let them know that the package manager of their 22.04 OS has issues.