Linode actually made this remarkably easy to do, I just had to:

• Shut down the old vm
• Resize its disk to be less than half of my Linode disk quota
• Create a new 12.04 disk image, again with less than half my Linode disk quota
• Launch the vm but now from the 12.04 image, and mount the old disk into the new server
• Copy everything over from the old disk image

My entire installation is ad-hoc, and I probably should have taken this opportunity to restore from my hacked-up backups and make sure that that works, but instead I signed up for Linode’s $5/month backup service.