internal error cannot create rule since ebtables tool is missing

I installed the bexar release of nova on a fresh instance of lucid running inside VMWare Fusion. Installation was via packages, using the ppa:nova-core/release repository.

Everything installed properly, but when I try to launch the ttylinux test image, it failed to come up. I got the following error reported by /var/log/nova/nova-compute.log:

2011-02-08 17:51:04,541 INFO nova.virt.libvirt_conn [-] instance instance-00000001: Creating image
2011-02-08 17:51:06,335 INFO nova.virt.libvirt_conn [-] instance instance-00000001: injecting key into image ami-vnm5880d
libvir: Network Filtererror : internal error cannot create rule since ebtables tool is missing.
2011-02-08 17:51:11,652 ERROR nova.exception [-] Uncaught exception
(nova.exception): TRACE: Traceback (most recent call last):
(nova.exception): TRACE: File "/usr/lib/pymodules/python2.6/nova/exception.py", line 116, in _wrap
(nova.exception): TRACE: return f(*args, **kw)
(nova.exception): TRACE: File "/usr/lib/pymodules/python2.6/nova/virt/libvirt_conn.py", line 410, in spawn
(nova.exception): TRACE: self._conn.createXML(xml, 0)
(nova.exception): TRACE: File "/usr/lib/python2.6/dist-packages/libvirt.py", line 1289, in createXML
(nova.exception): TRACE: if ret is None:raise libvirtError('virDomainCreateXML() failed', conn=self)
(nova.exception): TRACE: libvirtError: internal error cannot create rule since ebtables tool is missing.
(nova.exception): TRACE:
2011-02-08 17:51:11,657 ERROR nova.compute.manager [QJHBM06S7ATHYVS1NQQI anne IRT] instance 1: Failed to spawn
(nova.compute.manager): TRACE: Traceback (most recent call last):
(nova.compute.manager): TRACE: File "/usr/lib/pymodules/python2.6/nova/compute/manager.py", line 211, in run_instance
(nova.compute.manager): TRACE: self.driver.spawn(instance_ref)
(nova.compute.manager): TRACE: File "/usr/lib/pymodules/python2.6/nova/exception.py", line 122, in _wrap
(nova.compute.manager): TRACE: raise Error(str(e))
(nova.compute.manager): TRACE: Error: internal error cannot create rule since ebtables tool is missing.
(nova.compute.manager): TRACE:
libvir: QEMU error : Domain not found: no domain with matching name 'instance-00000001'

Note that ebtables is installed:

$ dpkg -s ebtables
Package: ebtables
Status: install ok installed
Priority: optional
Section: net
Installed-Size: 428
Maintainer: Ubuntu Developers <email address hidden>
Architecture: amd64
Version: 2.0.9.1-1
Depends: libc6 (>= 2.4)
Recommends: iptables
Conffiles:
 /etc/ethertypes 94bffde8f75a1b8f891fb780bfe15ca2
 /etc/init.d/ebtables 2fa905905a24f358428b713e6708620b
 /etc/default/ebtables 4b49d534ccce3c32252e3ac080b8997a
Description: Ethernet bridge frame table administration
 Ebtables is used to set up, maintain, and inspect the tables of
 Ethernet frame rules in the Linux kernel. It is analogous to iptables,
 but operates at the MAC layer rather than the IP layer.
Original-Maintainer: Jochen Friedrich <email address hidden>

$ sudo service ebtables status
 * Ebtables support available, number of installed rules [ OK ]

The only configuration change I made was to add the following line to /etc/nova/nova.conf: --libvirt_type=qemu