Hmmm. I think we're getting close to it, pal.
I had that problem too, and I googled a lot to find out how to fix that. I can't recall what I did, but it had to do with the keys. The problem was that I installed freenx without the "--setup-nomachine-key", and it persisted even though I corrected that.
When you first installed freenx, did you run the setup with "--setup-nomachine-key"?
If not, maybe we should delete the files it created in the process.
Take a look at this interesting discussion
Note that this is a discussion on RedHat, I think it will be a little different on ubuntu.
See if you have:
Fire the nxclient again.
cd <directory where the key is located>
sudo mv client.id_dsa.key client.id_dsa.key.bak
sudo nxsetup --setup-nomachine-key
Now, if you had used the "--setup-nomachine-key" in the first place, I would uninstall the freenx (sudo apt-get remove --purge freenx nxclient nxserver nxproxy nxagent) and clean-install it again.
Just a tip: try to copy a significant part of the error message into google and see what you find. That's what I usually do.
Anyway, tell us what you got there.