I can report the same bug:

root@hal9000:~# ubuntu-vm-builder kvm intrepid --arch 'amd64' --mem '512' --rootsize '4096' --swapsize '1024' --kernel-flavour 'virtual' --hostname 'ubuntu' --mirror 'http://archive.ubuntu.com/ubuntu' --components 'main,universe'
2009-02-24 13:08:24,030 INFO     Creating disk image: /tmp/vmbuilderhUXKaQ/disk0.img
2009-02-24 13:08:24,049 INFO     Adding partition table to disk image: /tmp/vmbuilderhUXKaQ/disk0.img
2009-02-24 13:08:24,110 INFO     Adding type 1 partition to disk image: /tmp/vmbuilderhUXKaQ/disk0.img
2009-02-24 13:08:24,123 INFO     Adding type 3 partition to disk image: /tmp/vmbuilderhUXKaQ/disk0.img
2009-02-24 13:08:24,131 INFO     Creating loop devices corresponding to the created partitions
2009-02-24 13:08:24,139 INFO     /proc/misc: No entry for device-mapper found
2009-02-24 13:08:24,139 INFO     Is device-mapper driver missing from kernel?
2009-02-24 13:08:24,140 INFO     Failure to communicate with kernel device-mapper driver.
2009-02-24 13:08:24,140 INFO     /proc/misc: No entry for device-mapper found
2009-02-24 13:08:24,140 INFO     Is device-mapper driver missing from kernel?
2009-02-24 13:08:24,141 INFO     Failure to communicate with kernel device-mapper driver.
2009-02-24 13:08:24,141 INFO     Incompatible libdevmapper 1.02.20 (2007-06-15)(compat) and kernel driver
2009-02-24 13:08:24,141 INFO     device mapper prerequisites not met
2009-02-24 13:08:24,141 INFO     Cleaning up
Traceback (most recent call last):
  File "/usr/bin/ubuntu-vm-builder", line 29, in <module>
    VMBuilder.run()
  File "/usr/lib/python2.5/site-packages/VMBuilder/__init__.py", line 66, in run
    frontend.run()
  File "/usr/lib/python2.5/site-packages/VMBuilder/plugins/cli/__init__.py", line 67, in run
    vm.create()
  File "/usr/lib/python2.5/site-packages/VMBuilder/vm.py", line 453, in create
    raise e
VMBuilder.exception.VMBuilderException: Process (['kpartx', '-av', '/tmp/vmbuilderhUXKaQ/disk0.img']) returned 1. stdout: , stderr: /proc/misc: No entry for device-mapper found
Is device-mapper driver missing from kernel?
Failure to communicate with kernel device-mapper driver.
/proc/misc: No entry for device-mapper found
Is device-mapper driver missing from kernel?
Failure to communicate with kernel device-mapper driver.
Incompatible libdevmapper 1.02.20 (2007-06-15)(compat) and kernel driver
device mapper prerequisites not met

And after probing the device mapper module:

root@hal9000:~# modprobe dm_mod
root@hal9000:~# ubuntu-vm-builder kvm intrepid --arch 'amd64' --mem '512' --rootsize '4096' --swapsize '1024' --kernel-flavour 'virtual' --hostname 'ubuntu' --mirror 'http://archive.ubuntu.com/ubuntu' --components 'main,universe'
2009-02-24 13:12:14,170 INFO     Creating disk image: /tmp/vmbuilder-_1bVM/disk0.img
2009-02-24 13:12:14,174 INFO     Adding partition table to disk image: /tmp/vmbuilder-_1bVM/disk0.img
2009-02-24 13:12:14,222 INFO     Adding type 1 partition to disk image: /tmp/vmbuilder-_1bVM/disk0.img
2009-02-24 13:12:14,230 INFO     Adding type 3 partition to disk image: /tmp/vmbuilder-_1bVM/disk0.img
2009-02-24 13:12:14,238 INFO     Creating loop devices corresponding to the created partitions
2009-02-24 13:12:14,247 INFO     Creating file systems
2009-02-24 13:12:14,284 INFO     mke2fs 1.40.8 (13-Mar-2008)
2009-02-24 13:12:14,767 INFO     Mounting target filesystems
2009-02-24 13:12:14,771 INFO     Installing guest operating system. This might take some time...
2009-02-24 13:12:14,794 INFO     Cleaning up
Traceback (most recent call last):
  File "/usr/bin/ubuntu-vm-builder", line 29, in <module>
    VMBuilder.run()
  File "/usr/lib/python2.5/site-packages/VMBuilder/__init__.py", line 66, in run
    frontend.run()
  File "/usr/lib/python2.5/site-packages/VMBuilder/plugins/cli/__init__.py", line 67, in run
    vm.create()
  File "/usr/lib/python2.5/site-packages/VMBuilder/vm.py", line 453, in create
    raise e
VMBuilder.exception.VMBuilderException: Process (['/usr/sbin/debootstrap', '--arch=amd64', 'intrepid', '/tmp/vmbuilder-_1bVM/root', 'http://archive.ubuntu.com/ubuntu']) returned 1. stdout: E: No such script: /usr/share/debootstrap/scripts/intrepid
, stderr:

I did not reboot after installing vm-builder
Here some info on the machine

root@hal9000:~# lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description:    Ubuntu 8.04.2
Release:        8.04
Codename:       hardy

root@hal9000:~# uname -a
Linux hal9000 2.6.24-22-server #1 SMP Mon Nov 24 20:06:28 UTC 2008 x86_64 GNU/Linux