You are right in supposing that the problem is with the XmNcolormap
(XtNcolormap for truly literate beings) not being set.  What you want
to do is start your application with your new colormap.  This can be a
chicken and egg sort of problem, however.  If you look at the Xt FAQ
there is an example that should show how it can be done.  If not, let
me know and maybe I can improve the example.

--pete