(or alternatively how I lost 3 days of my life)

Alright. I started with a base install of Dapper LTS. These steps should also work for a base install of non-server Ubunutu:

0. sudo -s will get you into a su session.
1. apt-get upgrade
2. apt-get install openssh-server
3. apt-get install ubuntu-desktop
4. test ssh with ssh user@<serverIP>
5. startx (to test, and then I just open a terminal and continue)
6. vi /etc/apt/sources.list and enable the universe repositories by uncommenting:

deb http://us.archive.ubuntu.com/ubuntu/ dapper universe
deb-src http://us.archive.ubuntu.com/ubuntu/ dapper universe

and add:

deb http://free.linux.hp.com/~brett/seveas/freenx dapper-seveas freenx
deb-src http://free.linux.hp.com/~brett/seveas/freenx dapper-seveas freenx

save and exit.
7. add the repository key (optional)
wget http://free.linux.hp.com/~brett/seve...x/1135D466.gpg -0- |sudo apt-key add -
8. apt-get update
9. install the packages
apt-get install freenx nxclient nxplugin
select custom keys during the install
10 add a new user to use with the freenx login
adduser <remoteuser>
11. setup up the nxserver
nxsetup
Hit enter to setup
Select yes for custom keys
Type yes quickly during key generation. If you miss it just re-run the nxsetup
12. cd /home/<remoteuser>
13. nxserver --adduser <remoteuser>
14. nxserver --passwd <remoteuser>
15. test the setup locally by running the client
/usr/NX/bin/nxclient
16. It should bring up a client wizard.
Name the session, enter the IP of the server. Hit the configure button.
On the first tab, select Key and then import. The key is here: /var/lib/nxserver/home/.ssh/client.id_dsa.key
On the advanced tab, check the enable SSL encryption of all traffic.
17. Use only the 1.5 clients, as the 2.0 client don't work unless you mess with the node config file. 1.5 works well and is stable with this server version.

You can find the 1.5 client for windows at http://www.industrial-statistics.com/info/nxclients

A few good things to know for trouble shooting:
nxserver --history or --version or --status
logs: /var/log/auth.log or nxserver.log or Xorg.0.log or messages.

Hope this helps!