Я ставил по этой статье:
http://www.altlinux.org/FreeNXи ничего больше лишнего не делал. Там правда есть опечатки, но они настолько явные, что видны даже мне, полному чайнику в линуксе. (- вместо -- в параметрах, после подключения сизифа надо отключить основной репозиторий, ну и т.п...)
Поправка на версию 4.1 Desktop:
LZMA делать уже не надо,
/sbin по умолчанию в путях не прописан (мелкий ляп этой сборки, но противный и непонятный...), пришлось его на скорую руку вручную добавлять для каки-то приведённых там команд...
Виндовый клиент nxclient-3.2.0-13.
И одинаковость раскладки проверьте на сервере и клиенте (из другой оперы, правда, но в соединении по связке VNC-RDP народ иногда упоминал о неприятностях при несовпадении раскладок)
Всё, вроде ничего больше...
Времени - 15 минут при установленной системе.
Попробуйте сначала сделать именно так: стандартно и с вин-клиентом, пусть заработает, а там уже заменяя поотдельности можно выцепить ошибку.