Bon, apparemment, problème spécifique aux VPS de Gandi. Il faut changer la méthode de démarrage du disque depuis l'espace client.
La méthode était "raw (xen)" (je ne sais pas du tout si c'était normal avant), j'ai mis "grub-x86_64 (xen)" et la chenille, pardon, la machine, redémarre.

Ça me rappelle https://savannah.gnu.org/bugs/?65503#comment2 mais c'est un contournement à déployer par les admins plutôt que quelque chose déjà intégré dans la distribution (à ma connaissance).