There was effective breakage between kernel-2.6.32-71.29.1.el6 and kernel-2.6.32-131.el6. When going from 6.0 to 6.1, the result is that if your Xen domain configuration file specified sda1 as a device name, it was previously renamed to xvda1. After 2.6.32-131.el6, the device is named xvde1 instead (because the names xvda - xvdd are reserved for hda - hdd device remapping). In situations where the configuration file explicitly lists "xvda1" or uses "hda1", "xvda1" continues to work.
So it seems that there are multiple workarounds to the problem, and it will be fixed in the 6.3 kernel, which is all good. However, I have to say that it's finally made me understand why some of my coworkers prefer their "single kernel" project, which aims to provide one kernel / ramdisk which can properly boot several distros on several hypervisors. I'm still partial to running the distro-provided kernel whenever possible, but having a known-good fallback that will at least be able to access the root filesystem & network is nice, so thanks to the Eucalyptus Support / IT team for working on that.