The problem
The gnome menu is being displayed but is not clickable from a vnc viewer session.
The solution
After a lot of digging on www.fedoraforum.org I found this:
Hi again all,
I have determined that a solution (albeit a bit crude) to this is to start your headless box in runlevel 3 (init 3) and then run gdm --no-console. This effectively (as I understand it) runs GDM in the background, and allows VNC to work fine.