Encontrei a causa do meu problema e estou postando aqui, caso isso possa ajudar qualquer outra pessoa a encontrar-se em uma situação semelhante.
Verifique se o nome do host é o mesmo em ambos /etc/hosts
e /etc/hostname
. Por alguma razão, eles eram diferentes no meu servidor - corrigido isso e o avahi agora está funcionando como pretendido.