Had same issue here, except setting 'encrypt passwords and keystrokes only' DID fix it for me - but only after changing my choice of VNC Server software for windows to TightVNC. With RealVNC there was no chance. Possibly the same strategy may work for Linux... (altho not with tightvnc as that creates it's own desktop session rather than exposing an existing one - depends what you're after).
I am already running TightVNC on all my Windows clients. On Ubuntu Desktop clients I'm using the built-in remote desktop package vino. Up until now vino has always worked fine with the default settings.
I just want to be able to view & control the existing GUI session on client desktops -- it saves me a lot running up & down stairs. But apparently ARD thinks I don't get enough exercise.