I had similar problems on a headless Debian box. The free version of NoMachine 4 only shares the physical screen. In my case Debian booted up with a default VGA configuration (640×480), totally useless for doing any work, but at least a connection. The Workstation license enables virtual desktops, this allows you to connect to the remote box using a screen with the same resolution as your client computer.
This configuration works OK for me, however personally I would prefer XRANDR support so I can resize the client window size.