I had the same exact problem in Debian Lenny, which I asked about in Xen mailing list. It was solved simply by loading xenblktap and creating a symlink to tapdisk binary.
Anyway also now with Xen 4 and Debian Squeeze (6.0.5), I cann't get a DomU working with tap:aio or tap:tapdisk:aio (or ???). It just works with file: URI (loop driver) which AFAIK not good for production.
(It just hangs in XENBUS: Waiting for devices to initialise: 295s...290s...285s...)
uname -a: Linux xen1 2.6.32-5-xen-686 #1 SMP Sun May 6 07:43:49 UTC 2012 i686 GNU/Linux
ii libc6-xen 2.11.3-3 Embedded GNU C Library: Shared libraries [Xen version]
ii libxenstore3.0 4.0.1-5.2 Xenstore communications library for Xen
ii linux-image-2.6.32-5-xen-686 2.6.32-45 Linux 2.6.32 for modern PCs, Xen dom0 support
ii linux-image-xen-686 2.6.32+29 Linux for modern PCs (meta-package), Xen dom0 support
ii xen-hypervisor-4.0-i386 4.0.1-5.2 The Xen Hypervisor on i386
ii xen-tools 4.2-1 Tools to manage Xen virtual servers
ii xen-utils-4.0 4.0.1-5.2 XEN administrative tools
ii xen-utils-common 4.1.2-6 Xen administrative tools - common files
ii xenstore-utils 4.0.1-5.2 Xenstore utilities for Xen