I decided that I should access my server using NoMachine's NX rather that VNC like I normally do as it uses a more efficient protocol and I can easily secure the connection, without having to tunnel things through SSH.
Installation of FreeNX was easy enough, but I ran into SELinux issues which meant that I was unable to log in. A HowTo on the Fedora forums helped with that, and also noted some library links that needed to be created. After following these instructions I was able to log in using the Windows NX client, but kept getting session failure errors.
After Googling and trying various things for an hour or so I came across ehyme's blog entry describing how to set up NX on Fedora, which I'd highly recommend reading. I read this, installed NoMachine's rpms and got to the same situation as with FreeNX, although it was much easier this time.
After a few more attempts I eventually fixed the problem by unchecking the Disable encryption of all traffic checkbox under the Advanced configuration tab. That made the session errors go away.
I am sticking with NoMachine's rpms for now as they are a later version, but I expect this would have resolved the FreeNX issue too.
Update: NoMachine News has an Ubuntu 8.10 and Fedora 10 Bug Issues Update entry on 2009-01-15. This includes some session errors so maybe this was the reason I was having issues with FreeNX. Installing at least version 3.3.0 is recommended as this includes the fixes.