Разобрался.
Проблема в том, что изменилось расположение startkde, которое в node.conf прописано по умолчанию.
Прописал правильное (КДЕ4): /usr/lib/kde4/bin/startkde и все заработало.
Думаю, что надо это поправить и в конфиге по умолчанию. А то nxserver работает из коробки без лишних телодвижений, кроме этого. Кстати, может быть добавить линки по старым путям? А то также изменилось расположение konqueror-a, dolphin-a и пр. Кроме того по умолчанию не прописан в путях новый каталог (/usr/lib/kde4/bin/) поэтому не запускаются из комстроки тот же самый konqueror.
ЗЫ Нашел аналогичный баг на багзиле, но пока не могу отписать - мыльный сервер, на котором ящик опять в дауне, блин, а пароль не помню.
https://bugzilla.altlinux.org/show_bug.cgi?id=21959