I had this same issue. I even used the process explorer and saw that lsass.exe was not running in protected mode. I resolved my issue and it does appear to be an issue on NoMachine’s side. My versions are Windows 6.3.6 server and Debian 6.3.6 client.
The issue I had was that the key was in the new format (i.e. I used ‘-o’ when creating the key).
The workaround was that I created a new key pair (without the ‘-o’ flag), appended the new public key to the server authorized.crt, and now it is working.
The solution would be for NoMachine to support the new key formats.
Hope this helps in the meantime!