I don't have any knowledge in this area to provide any useful info.

One difference is that I have dmenu installed as a separate standalone
package, but my windows manager is whatever default comes with RHEL
6.6/Gnome.

But it looks like the OP has installed the i3 WM (dmenu is shipped along as
a part of i3). So the problem could be at a lower level than dmenu.