Had same problem in Feisty
Still have same problem in Gutsy current (dist-upgraded Feisty --> Gutsy)

This is not limited to Gajim, as others have said

My avahi services do not get started reliably.  Sometimes, after rebooting, they start.  4 out of 5 times, they do not.  I will give some outputs of relevant logs for when they start and when they don't start below.

First, a workaround or solution until this gets fixed:
I found that restarting the avahi services using "/etc/init.d/avahi-daemon restart" did NOT help
Just by luck, I noticed that if I modify /etc/avahi/avahi-daemon.conf, the daemon detects this change and reloads itself.  After reloading, my services work properly.
So, I added a simple command "sleep 2 && touch /etc/avahi/avahi-daemon.conf" to the 'start' case of /etc/init.d/avahi-daemon (line 56), as shown below:

d_start() {
    modprobe capability >/dev/null 2>&1 || true

    $DAEMON -c && return 0

    if [ -e ${DISABLE_TAG} ]; then 
      # Disabled because of the existance of an unicast .local domain
      log_warning_msg "avahi-daemon disabled because there is a unicast .local domain"
      exit 0;
    fi;

    $DAEMON -D

    ## Added to force reload of avahi-daemon.conf and therefore reliable establishment of services
    sleep 2 &&  touch /etc/avahi/avahi-daemon.conf
    ## End added command
    
}


Now my syslog looks like this (and services work):
pr  5 16:59:00 mythtvbox avahi-daemon[13843]: Leaving mDNS multicast group on interface eth1.IPv4 with address 192.168.2.119.
Apr  5 16:59:01 mythtvbox kernel: [ 3159.321157] Failure registering capabilities with primary security module.
Apr  5 16:59:01 mythtvbox avahi-daemon[14103]: Found user 'avahi' (UID 105) and group 'avahi' (GID 111).
Apr  5 16:59:01 mythtvbox avahi-daemon[14103]: Successfully dropped root privileges.
Apr  5 16:59:01 mythtvbox avahi-daemon[14103]: avahi-daemon 0.6.20 starting up.
Apr  5 16:59:01 mythtvbox avahi-daemon[14103]: Successfully called chroot().
Apr  5 16:59:01 mythtvbox avahi-daemon[14103]: Successfully dropped remaining capabilities.
Apr  5 16:59:01 mythtvbox avahi-daemon[14103]: Loading service file /services/afpd-guest.service.
Apr  5 16:59:01 mythtvbox avahi-daemon[14103]: Loading service file /services/afpd-reg.service.
Apr  5 16:59:01 mythtvbox avahi-daemon[14103]: Loading service file /services/samba.service.
Apr  5 16:59:01 mythtvbox avahi-daemon[14103]: Joining mDNS multicast group on interface eth1.IPv4 with address 192.168.2.119.
Apr  5 16:59:01 mythtvbox avahi-daemon[14103]: New relevant interface eth1.IPv4 for mDNS.
Apr  5 16:59:01 mythtvbox avahi-daemon[14103]: Network interface enumeration completed.
Apr  5 16:59:01 mythtvbox avahi-daemon[14103]: Registering new address record for fe80::2a0:ccff:fed0:b6ca on eth0.*.
Apr  5 16:59:01 mythtvbox avahi-daemon[14103]: Registering new address record for fe80::20e:a6ff:fe9f:c091 on eth1.*.
Apr  5 16:59:01 mythtvbox avahi-daemon[14103]: Registering new address record for 192.168.2.119 on eth1.IPv4.
Apr  5 16:59:01 mythtvbox avahi-daemon[14103]: Server startup complete. Host name is mythtvbox.local. Local service cookie is 2787383504.
Apr  5 16:59:01 mythtvbox avahi-daemon[14103]: Registering HINFO record with values 'I686'/'LINUX'.
Apr  5 16:59:03 mythtvbox avahi-daemon[14103]: Files changed, reloading.
Apr  5 16:59:03 mythtvbox avahi-daemon[14103]: Service "mythtvbox SMB" (/services/samba.service) successfully established.
Apr  5 16:59:03 mythtvbox avahi-daemon[14103]: Service "mythtvbox AFP (secure)" (/services/afpd-reg.service) successfully established.
Apr  5 16:59:03 mythtvbox avahi-daemon[14103]: Service "mythtvbox AFP (guest)" (/services/afpd-guest.service) successfully established.


Without this workaround, my syslog looked like this (note the lack of "successfully established" lines):


Apr  5 17:01:09 mythtvbox avahi-daemon[14103]: Leaving mDNS multicast group on interface eth1.IPv4 with address 192.168.2.119.
Apr  5 17:01:09 mythtvbox kernel: [ 3287.653867] Failure registering capabilities with primary security module.
Apr  5 17:01:09 mythtvbox avahi-daemon[14215]: Found user 'avahi' (UID 105) and group 'avahi' (GID 111).
Apr  5 17:01:09 mythtvbox avahi-daemon[14215]: Successfully dropped root privileges.
Apr  5 17:01:09 mythtvbox avahi-daemon[14215]: avahi-daemon 0.6.20 starting up.
Apr  5 17:01:09 mythtvbox avahi-daemon[14215]: Successfully called chroot().
Apr  5 17:01:09 mythtvbox avahi-daemon[14215]: Successfully dropped remaining capabilities.
Apr  5 17:01:09 mythtvbox avahi-daemon[14215]: Loading service file /services/afpd-guest.service.
Apr  5 17:01:09 mythtvbox avahi-daemon[14215]: Loading service file /services/afpd-reg.service.
Apr  5 17:01:09 mythtvbox avahi-daemon[14215]: Loading service file /services/samba.service.
Apr  5 17:01:09 mythtvbox avahi-daemon[14215]: Joining mDNS multicast group on interface eth1.IPv4 with address 192.168.2.119.
Apr  5 17:01:09 mythtvbox avahi-daemon[14215]: New relevant interface eth1.IPv4 for mDNS.
Apr  5 17:01:09 mythtvbox avahi-daemon[14215]: Network interface enumeration completed.
Apr  5 17:01:09 mythtvbox avahi-daemon[14215]: Registering new address record for fe80::2a0:ccff:fed0:b6ca on eth0.*.
Apr  5 17:01:09 mythtvbox avahi-daemon[14215]: Registering new address record for fe80::20e:a6ff:fe9f:c091 on eth1.*.
Apr  5 17:01:09 mythtvbox avahi-daemon[14215]: Registering new address record for 192.168.2.119 on eth1.IPv4.
Apr  5 17:01:09 mythtvbox avahi-daemon[14215]: Server startup complete. Host name is mythtvbox.local. Local service cookie is 3394920652.
Apr  5 17:01:09 mythtvbox avahi-daemon[14215]: Registering HINFO record with values 'I686'/'LINUX'.

........and that's it .... it never says "Service blah-blah-blah successfully established"

My services, syslog, dmesg and avahi-daemon.conf are attached.

-- Fisslefink