Turns out the provider has a custom initrd that does the /lib/modules mount. I don't know how common this is for VPS providers. Could the "Probably this system is using User Mode Linux." prompt check if /lib/modules is in /etc/fstab, and if not, offer a different suggestion, e.g. something like the steps I took.
- Bug#1034346: usrmerge: fails to install on Xen VPS ... Hans-Christoph Steiner
- Bug#1034346: usrmerge: fails to install on Xen... Marco d'Itri
- Bug#1034346: usrmerge: fails to install on... Hans-Christoph Steiner
- Bug#1034346: usrmerge: fails to instal... Marco d'Itri
- Bug#1034346: usrmerge: fails to in... Hans-Christoph Steiner
- Bug#1034346: more info Hans-Christoph Steiner