I'm running a headless box, so I installed nxserver-freenx without installing any real X server. There were a few problems with this setup involving fonts and, most importantly, keymapping.
After days of struggling with the problem I installed xorg-server and the problems cleared right up.
Either xorg-server or some dependency thereof should be listed as a dependency of nxserver-freenx.
Steps to Reproduce:
1. Install nxserver-freenx on a more or less blank slate of a computer
2. Attempt to connect
Quirky behavior including mismapped keyboard
Good behavior right off the bat.
Last rites in progress in bug #537774