My mobo is the Via Epia EN12000 with a Via C7 Esther CPU, and only has the cmov CPU flag, so no chance of getting HVN working. I had to build the standard Gentoo Xen Linux Sources at version 2.6.20. That's better than the stock Xen Kernel which is currently 2.6.18, but it still doesn't have specific support for the Via C7. Not a problem though.
I have an old Debian Sarge that hasn't been updated in a while. To get it working I had to add the sarge-backports source to /etc/apt/sources.list. Once that was done it was still a bit of a problem getting a Xen kernel installed. In the end I figured out the dependencies to work.
Aptitude didn't give very helpful details so I had to get the info I needed by using "dpkg -i" on packages. Eventually the following commands got me where I wanted to get:
aptitude install klibc-utils
aptitude -V -f install udev=0.105-4~bpo.1
aptitude -V -f install initramfs-tools
aptitude -V -f install linux-image-2.6-xen-686
The key to this seems to have been the packages removed and installed by klibc-utils. After that you could probably skip to installing linux-image-2.6-xen-686.
For reference, the main error from aptitude that was killing me was:
The following packages have unmet dependencies:
initramfs-tools: Depends: udev (>= 0.086-1) but it is not installable
even though udev-0.105-4~bpo.1 was installed.
Once the kernels were installed I tried to boot the domain in Xen and faced another problem. The linux-image-2.6.18-4-xen-686 in Sarge Backports now supports PAE, so I had to rebuild my dom0 kernel and apps-emulation/xen with PAE support.