I had a similar problem to this myself once setting up vnc on a version of Linux. It turned out that the scripts that started the Xwindows servers didn't have the correct path to the fonts. Once I fixed that it worked just fine.
I don't know what version of vnc you are using but you might try editing the vncserver script to include the explicit paths to the fonts to see if that helps. In the version I use (TightVNC on RHEL5) there is a portion of the script that sets up the exact command issued to start the vnc Xwindows system (Xvnc). As part of this setup there is a line (commented out in my current version) that sets the font path with the -fp flag. The code snippet in question looks like this:
# Now start the X VNC Server
$cmd = "Xvnc :$displayNumber";
$cmd .= " -desktop " . "edString($desktopName);
$cmd .= " -httpd $vncJavaFiles" if ($vncJavaFiles && ! $nohttpd);
$cmd .= " -auth $xauthorityFile";
$cmd .= " -geometry $geometry" if ($geometry);
$cmd .= " -depth $depth" if ($depth);
$cmd .= " -pixelformat $pixelformat" if ($pixelformat);
$cmd .= " -rfbwait 30000";
$cmd .= " -rfbauth $vncUserDir/passwd";
$cmd .= " -rfbport $vncPort";
$cmd .= " -pn";
# Add font path and color database stuff here, e.g.:
#
# $cmd .= " -fp /usr/lib/X11/fonts/misc/,/usr/lib/X11/fonts/75dpi/";
# $cmd .= " -co /usr/lib/X11/rgb";
#
The line to set the font path is in the commented out section at the end. You might try finding the similar section in your start-up script and explicitly setting the paths to the fonts to see if that will at least get you past the fatal error.