If you are using Redhat.. Xconfigurator is definitely the way to go. You can also use the text based config utility called 'xf86config' with just about any distribution including Redhat. You will need to know the chipset and brand of your video card, the amount of video RAM and things like that. If you are using SUSE there is something called "SAX" that will do the same thing that Xconfigurator does for Redhat.
In any event, you can use any of these to setup Xwindows for the screen resolutions and color depth you want. Another, less atractive option would be to simply edit the 'XF86Config' file by hand. Post the contents of your '/etc/X11/XF86Config' and '/etc/X11/XF86Config-4' file if you have them and maybe we can tell you how to edit them if it comes to that.