The emacs-nox package would appear to require locale information (it is specifically looking for /usr/lib/X11/locale/locale.alias) from the XFree86 package. On a non-X installation for a server, emacs complains that it can not find that file. Packages: emacs-20.4-4 emacs-nox-20.4-4
Strace shows that this happens with the version shipped with Red Hat Linux 6.1, but not the one shipped with Red Hat Linux 6.2. The releases are binary compatible, so you should be able to just upgrade that package.