After a few too many minutes spent digging into this error message and not finding any applicable answers, I looked into the NX session log file in my user home directly to see:
/usr/NX/bin/nxagent: error while loading shared libraries: libXpm.so.4: cannot open shared object file: No such file or directory
Because this is a newly installed server (RedHat/CentOS 5.3), and even though I had installed the 'xorg-x11-xauth' and 'gnome-desktop' packages, this required library somehow got missed. To install this missing library, you need to install the 'libxpm' package. In my case, using yum:
yum install libXpm
And while you're at it, make sure that the full Xorg x11 server is installed. Oddly, 'gnome-desktop' does not depend on this package:
yum install xorg-x11-server-Xorg
