Tenho quase certeza de que o Vinagre, a ferramenta interna de visualização do VNC, possui excelente suporte a avahi (também conhecido como mDNS ou ZeroConf). Bonjour, que é a versão da Apple do Avahi, é razoavelmente compatível. Eu usei tanto para compartilhamento de biblioteca do iTunes do Mac para Ryhthmbox e compartilhamento VNC - pelo menos nos dias que eu ainda usava Macs (cerca de dois anos atrás).
No entanto, apenas para descartar um bug no Vinagre, tente o (eu acho) ainda melhor Remmina para ver se ele pode se conectar:
sudo apt-get install remmina remmina-gnome
Você também pode ver o que está sendo transmitido em sua rede com o avahi-utils. Você pode instalá-lo com
sudo apt-get install avahi-utils
Depois, veja o que está sendo executado na sua rede com
avahi-browse -a
Eu também devo acrescentar que Avahi apenas anuncia a conexão. Você ainda precisa saber a senha para se conectar - isso é definido nas configurações do Mac. De este mais velho postagem no blog :
E você não precisa para usar o Avahi se você já souber o endereço IP do próprio Mac. Basta colocá-lo em um novo perfil de conexão no Vinagre ou Remmina e você será capaz de especificar a senha e se conectar dessa maneira. Como eu digo, Avahi apenas anuncia o serviço em toda a sua rede local.