NoMachine once generated high expectations in the Linux world. Their focus nowadays seems to be on commercial users.
Thanks for the link. I've actually been pleasantly surprised by Xvnc over an "ssh -C" tunnel. Additionally, there are some parameters you can set for the vncserver (man Xvnc... one example is "-deferUpdate") that can significantly improve performance for bad connections or awful X applications.
I've tried it several times over the years and still find standard vnc4server works great where nomachines seemed slower to me, and harder to install, you had to download directly from their web site.
Then you must have setup something wrong. NX has ALWAYS been consistently faster than a typical VNC setup. You also don't have to use NoMachine's implementation - use FreeNX (server) + OpenNX (client).