I'm fairly certain that Vinagre, the built in VNC viewer tool has excellent avahi (also known as mDNS or ZeroConf) support. Bonjour, which is Apple's version of Avahi is, from memory, reasonably compatible. I've used it both for iTunes library sharing from Mac to Ryhthmbox and VNC sharing - at least back in the days I still used Macs (about two years ago).
However, just to rule out a bug in Vinagre, try the (I think) even better Remmina to see if it can connect :
sudo apt-get install remmina remmina-gnome
You can also see what's being broadcast on your network with avahi-utils. You can install it with
sudo apt-get install avahi-utils
Then see what's running on your network with
I should also add that Avahi just advertises the conneciton. You'll still need to know the password to connect - that's set in the Mac settings. From this older blog post :
And you don't need to use Avahi at all if you already know the IP address of the Mac itself. Just stick it into a new connection profile on either Vinagre or Remmina and you'll be able to specify the password and connect that way. As I say, Avahi just advertises the service across your local network.