Debian Lenny expects udev on a vps that doesn't support it
Most Xen HowTos I've seen (HowToForge, debian.org) indicate that udev needs to be enabled at image creation by passing --role=udev to xen-create-image.
I doubt you can create an image that uses udev on a running system that doesn't support it, but it might be possible.
My best guess is that you should remove the udev package from your Lenny guest (apt-get remove udev), and let it use the old devfs. If you have packages that depend on udev, you may need to remove them and find alternatives that do not.