O Avahi precisa estar em execução nas duas máquinas. É o daemon que fornece serviços mDNS.
root @ rilindo-desktop: ~ # ps -ef | grep avahi avahi 903 1 0 Jan01? 00:00:05 avahi-daemon: registrando [rilindo-desktop.local] avahi 904 903 0 Jan01? 00:00:00 avahi-daemon: ajudante chroot raiz 18206 15276 0 11:23 pts / 2 00:00:00 grep avahi
Assumindo que a porta 5353 não seja filtrada / bloqueada nas máquinas, você precisará validar a configuração do avahi.