Köszönöm, megoldódott a probléma.
Miután elmolyolgattam vele pár órát, úgy döntöttem, hogy teljes egészében az említett leírást követem, tehát letöröltem az összes xen-es csomagot, és forrásból telepítettem, ha jól emlékszem, akkor a xen 3.4.2-öt.
Ezek után, már csak a python modulokkal volt gond. Ezek a site-packages könyvtárba települtek, de asszem a 9.10-estől az alapértelmezett könyvtár a dist-packages, és a python itt keresi az import utasításokra a modulokat, márpedig xen make install-nál a régi helyre települtek ezek, így aztán nem is lehetett használni semmit.
Van egy leírás, amely javasolja még fordítás előtt a symlinkelést - azaz a site-packages mutasson a dist-packages-re -, de miután erre már csak a fordítás után jöttem rá, egyszerűen csak átmásoltam mindent, és onnantól kezdve hibátlan volt. Volt net, sőt, miután egy vendég gépet is csináltam, azon is volt.
Nem tudom, hogy valójában mi volt a hiba, csak sejtem, hogy a kevert verziós telepítések okozhatták a problémát.
Össze foglalva, a 9.10-es ubuntu-server még nincs felkészítve a tisztán csomagból történő telepítésre, csupán a fent említett nagyon jó leírás igazított el.
Néhány link a témából, amelyek segítettek:
https://help.ubuntu.com/community/Xen
http://wiki.kartbuilding.net/index.php/Xen_Networking
http://cosi.clarkson.edu/docs/installingxen/