If you are using the CentOS version of NX / FreeNX, please test this version and provide feedback on this list. Barring any show stopping negative feedback, these RPMS will replace the current versions in CentOS extras in 2 weeks.
Here's one positive report from the "now it works again" dept:
After updating the NoMachine NX client (to nxclient-2.1.0-9) on a FC6 machine, I could not successfully connect to my CentOS 4.4 server using the old freenx/nx packages currently in CentOS Extras.
However, after an update on the CentOS server, using
yum --enablerepo=c4-testing update nx freenx
...connections work again. Before, the connection eventually failed due to some form of timeout. I didn't dig into the issue, since I stumbled onto your post and dediced to try out the updated packages just for kicks. Turns out the update did the trick.
In summary: the updated packages nx-2.1.0-2.c4 and freenx-0.5.0-11.c4 "just work" for me.