Acabei de instalar o nx-server em uma nova instalação do Ubuntu 11.10. Eu também segui as instruções como em Usando o NX com o Unity em 11.10 para especificar a sessão que eu quero carregar.
Funciona bem, e eu posso jogar com o unity-2d ou com o gnome-classic apenas mudando a configuração do nx-client.
Existe apenas um problema, ou seja, independentemente da sessão iniciada ou do tema escolhido nas configurações do sistema, os controles do gtk não são temáticos e são simplesmente feios. É como quando o gnome-settings-daemon não está em execução, se você sabe o que quero dizer (sim, verifiquei se estava em execução). A imagem postada na pergunta antes mencionada (embora mostrando um problema diferente) explica tudo.
Qualquer correção possível?
Eu não uso o Nomachine NX em alguns anos, mas posso confirmar que o X2go funciona, se você estiver disposto a experimentar outra solução do NX. O X2go é muito bom, com suporte ao PulseAudio e tudo mais.
Eu me lembro de um problema semelhante há alguns anos com o FreeNX. Naquela época, se bem me lembro, tinha algo a ver com o libxklavier, se você quer um ponto de partida.