I tried to answer the question from Mark:
Keymap issues with NX from Mac OS X Lion to Ubuntu
However, it is locked so I figured I would post a new question / answer.
I have been trying to answer this for a few days now because I have no issues when connecting through NX Client (technically OpenNX) to FreeNX server from an iMac (with Lion), but if I try to connect with a Macbook Pro I get horrible keyboard binding issues.
I had the same issue (I'am on a Macbook Air with OSX 10.7 Lion) and reverting back to 0.16.0.648 fixed the problem for me too.