The new VPS is still Trusty (14.04.3 now).
This setup is a bit better than previously since it's a Xen instance, has twice the RAM and I'm now able to run lxc (and, for minecraft, use an unprivileged lxc container). I had a backup of the minecraft server, so just copied that over. I then installed Oracle's Java 8 since that's what minecraft recommend.
sudo apt-get install software-properties-common
sudo add-apt-repository ppa:webupd8team/java
sudo apt-get update
sudo apt-get install oracle-java8-installer
sudo apt-get install libxrender1 libxtst6 libxi6
The last line above is needed since there's no headless option for java8 and when it starts it just requires some shared objects from those packages so it can link against them even though it'll never use them (since this is a VPS, and so, headless).
minecraft is running again now. We'll see whether the 2Ghz opterons on there are fast enough to keep up with the boys' redstone creations.
I am going to *HAVE* to set up an hourly backup regime though, with hourly rsync. The price of going with the cheapest VPS providers out there, they might not survive more than 6 months or so, and I need to be able to restore things on the next VPS in the chain.