I’ve always had an issue with Debian Lenny and connecting via ssh or local console (xm console --role udev to the end of your xen-create-image command, and then add extra = ‘xencons=tty1 console=tty1′ to the newly created cfg file in /etc/xen.
# xen-create-image --size 10G --ip 1.2.3.4 --netmask 255.255.255.0 --gateway 1.2.3.1 --hostname newvm --lvm vg --role udev
# echo "extra = 'xencons=tty1 console=tty1'" >> /etc/xen/newvm.cfg
More info can be found at http://wiki.debian.org/Xen under “Additional note for domU on lenny using xen-tools”. Note: I do not follow their guide exactly – this is just what has worked for me.