vmbuilder aborts with "locale-gen does not recognize your locale"

Trying to create a new vm, I get the following:

2010-02-17 22:01:03,177 DEBUG : add_part - begin 0, length 4096, end 4095
2010-02-17 22:01:03,177 DEBUG : add_part - begin 4096, length 1024, end 5119
2010-02-17 22:01:03,177 DEBUG : ip: dhcp
2010-02-17 22:01:03,182 DEBUG : Checking if --exec PATH exists: /tmp/vm-new-setup-negkZE
2010-02-17 22:01:03,182 DEBUG : Checking permissions of --exec PATH: /tmp/vm-new-setup-negkZE
2010-02-17 22:01:03,184 DEBUG : ['locale-gen', 'en_US.utf8']
2010-02-17 22:01:03,189 DEBUG : Oh, dear, an exception occurred
2010-02-17 22:01:03,190 INFO : Cleaning up
2010-02-17 22:01:03,190 DEBUG : ['rm', '/tmp/tmpLdrkFP']
locale-gen does not recognize your locale 'en_US.utf8'
error: failed to get domain 'test-karmic-amd64'
error: Domain not found: no domain with matching name 'test-karmic-amd64'
Problem creating virtual machine 'test-karmic-amd64' (doesn't exist)
ERRORS FOUND

ProblemType: Bug
Architecture: amd64
Date: Wed Feb 17 22:07:13 2010
DistroRelease: Ubuntu 10.04
EcryptfsInUse: Yes
NonfreeKernelModules: nvidia
Package: python-vm-builder 0.11.3-0ubuntu8
PackageArchitecture: all
ProcEnviron:
 PATH=(custom, user)
 LANG=en_CA.utf8
 SHELL=/bin/bash
ProcVersionSignature: Ubuntu 2.6.32-13.18-generic
SourcePackage: vm-builder
Uname: Linux 2.6.32-13-generic x86_64