Avahi-daemon fails to chroot with "Permission denied"

Avahi-daemon fails to chroot with "Permission denied"

I've got a problem with starting up avahi-daemon. There's some strange
difference between 6 hosts - 3 of them are in one rackspace region, 3 are
in another - but that's all that should be different between them.
When I start up avahi-daemon, I get back:
Found user 'avahi' (UID 106) and group 'avahi' (GID 112).
Successfully dropped root privileges.
avahi-daemon 0.6.31 starting up.
Failed to chroot(): Permission denied
avahi-daemon 0.6.31 exiting.
strace confirms it's only the chroot failing:
...
socket(PF_FILE, SOCK_STREAM, 0) = 8
unlink("/var/run/avahi-daemon/socket") = -1 ENOENT (No such file or
directory)
bind(8, {sa_family=AF_FILE, path="/var/run/avahi-daemon/socket"}, 110) = 0
listen(8, 128) = 0
umask(022) = 0
write(5, "W", 1) = 1
chroot("/etc/avahi") = -1 EACCES (Permission denied)
write(2, "Failed to chroot(): Permission d"..., 37) = 37
I tried to reproduce it with my own application, but everything works just
fine from a python shell:
>>> os.chroot('/etc/avahi')
>>> os.listdir('/')
['services', 'hosts', 'avahi-daemon.conf', 'avahi-daemon.conf.dpkg-dist']
The rest from what I can see is the same in strace logs between the hosts
- they drop the privileges using setresuid/setresgid, they call
capset(0x20080522, 0, {CAP_SYS_CHROOT, CAP_SYS_CHROOT, 0}) = 0, they try
to chroot("/etc/avahi")... and the ones in ORD region succeed, the ones in
LON fail.
Apparmor is running, but there are no profiles loaded for the avahi daemon.
/etc/avahi is of course +rx for everyone.
I'm completely lost here - what could be the reason?