Comment 6 for bug 107630

Ah-ha! I've tracked this down. The issue is with how the Feisty AppArmor replaces the "capability" module. If the "apparmor" module hasn't been built, "capability" can't load, meaning Avahi doesn't have what it needs to do its work.

So, the solutions are either:
1) run Gutsy (where this is fixed)
2) get the apparmor-modules built and install (see below)
3) uninstall AppArmor (which removes the /etc/modprobe.d/apparmor file)

Here's how to get your apparmor module installed again, after a kernel upgrade:

 sudo apt-get install apparmor-modules-source
 sudo m-a -v -t prepare
 sudo m-a -v -t -f build apparmor-modules
 sudo m-a -v -t install apparmor-modules
 modprobe apparmor