Here's what I had to do to get VNC working between my mac and my ubuntu linux machine here on this home network.
On the mac tiger, I went to http://sourceforge.net/projects/cotvnc/ and downloaded and installed the latest Chicken of the VNC.
On the ubuntu linux, I had to do this:
$ sudo apt-get update; sudo apt-get install tightvncserver
$ xset -q | less # look for the list of font paths and copy
$ sudo jed /etc/vnc.conf
# set $fontPath = what-you-copied-from-the-last-command
$ xrandr -q
You can use xrandr -q
just to find out a) what your current screen resolution is in Linux and what your alternatives are. With all this ready, then start the server.