The package I installed on Ubuntu was ‘NoMachine for Linux – amd64’ (http://web04.nomachine.com/download/4.0/Linux/nomachine_4.0.362_1_amd64.deb).
I currently don’t have XServer running, which is probably why it doesn’t work (especially that the instructions you pointed me to do contain some reference to the cookies, etc, which according to the log file is currently missing, which makes sense).
I wonder if the behavior of XServer has changed since version 3.5? I’m pretty sure everything was instantiated ‘on the fly’ and i wasn’t setting up xserver explicitly back then (through i did have different package installed on Ubuntu server – kubuntu-desktop if i’m not mistaken).