Got around to finally installing the FreeNX server on my Ubuntu server. Following this guide https://help.ubuntu.com/community/FreeNX got me most of the way there with one caveat, Authentication. In the last step of the guide where you run the nxsetup -install program, I got a problem where it claimed that the authentication wasnt working. Upon closer examination I discovered that the key file produced by the NX installer is not configured in SSH.
To allow NX to autheticate do the following in addition to the aforementioned guide.
# gksudo gedit /etc/ssh/sshd_config
Search for Add the following line: #AuthorizedKeysFile %h/.ssh/authorized_keys
Create a new line underneath it with the following: AuthorizedKeysFile /var/lib/nxserver/home/.ssh/authorized_keys2
Restart the ssh server
# sudo /etc/init.d/ssh restart
All should be up and running at this point ;)