I have been using Xen under Debian for a few years now (has it been that long?) and in my experience is is both straightforward to setup and rock solid.
In the early days I was using unofficial packages, but since Etch everything worked "out of the box". I have just upgraded to Lenny and so far (touch wood) it remains as robust as ever.
I have a nice 8GB dual-CPU Opteron server running 64-bit dom0 and domU's. This box does not support hardware virtualisation, so from my point of view Xen is the only option to get near-native speed and 64-bit guests.