I had this problem. After some digging, it turned out it was simply a problem of python-avahi not being installed. After installation, it seems to have resolved itself.
Since gajim without python-avahi isn't really a charm, why isn't python-avahi at least recommended (or depended) by gajim? (Now it's just suggested, which AFAIK isn't pulled in automatically by apt)
I had this problem. After some digging, it turned out it was simply a problem of python-avahi not being installed. After installation, it seems to have resolved itself.
Since gajim without python-avahi isn't really a charm, why isn't python-avahi at least recommended (or depended) by gajim? (Now it's just suggested, which AFAIK isn't pulled in automatically by apt)