Anders - While I don't know anything about EC2 booting, if HVM images boot as if they were a "standard" local disk and you're open to using GRUB, you might want to look at the GCE booting code. It was tricky to get GRUB bootstrapped in the right way, but I think what I ended up with works properly, including with the debian integration (i.e. update-grub and /etc/grub.d/* and /etc/default/grub ) going forward. This is one of the trickiest bits I've heard for other people getting from-scratch images to boot on GCE, but it's in no way specific to our cloud.
Specific links:
Note: Our images use a single partition for the OS at a 1 MB offset, before which GRUB presumably installs its embedded blocks. We install GRUB into the MBR. If you're using a markedly different arrangement, adjust accordingly.
A more minor note: lines 18-19 of 30-grub are broken, but it only affects the grub-level serial console and the obvious fix broke other stuff at a time when we were in "crunch mode" leading up to the Google Compute Engine general availability launch last month. I'm sure the correct fix is only slightly more work, but in any case you're on the Python side of things now so this is just inspiration.
- Jimmy