I got back to playing with Xen again now.
I set up a new box and installed xen via
apt-get install xen-linux-system-2.6.18-6-xen-686.
In the syslog I had heaps of errors like:
Feb 1 11:29:09 test33-10 kernel: 4gb seg fixup, process sshd (pid 2583), cs:ip 73:b7bd59bc
Feb 1 11:29:16 test33-10 kernel: printk: 261591 messages suppressed.
I found out that this was because of libc6-xen was missing. So installing this one, solved the problem for me.