Well, I'm not sure what editing tools you have available on Ubuntu, but really the easiest way to fix your problem IS to edit your xorg.conf file. Before you freak, I'll give you some pointers.
1) You have to be the root user to be able to edit the file. To do this, start up a terminal (the CLI) and type 'su' followed by the root password when asked for it. Your prompt should change from a '$' to a '#'.
2) The file you are looking for is at /etc/X11/xorg.conf. So, once you are root, issue the following command
(obviously don't type the '#' symbol)
3) Invoke your favorite text editor along with the name of the xorg file. My normal text editor is the pico program. You could also use vi, emacs, or any other program you wish.
4) Most assuredly the section you want is towards the bottom of the file. Scroll to the bottom. In the section marked 'Section "Screen"' you may see the following:
# DefaultDepth 8
# DefaultDepth 16
# DefaultDepth 32
In this case, all you need to do is put a '#' in front of the one you wish to not use and remove the '#' from the line you do wish to use. If you have only this
and no others, then that might mean you only have settings defined for 24-bit color depth. In this case add the desired depth and comment out the old one
# DefaultDepth 24
And look directly below this section. You should see a 'SubSection "Display"' section that defines the resolutions that can be used with whatever depth has been selected as default. If only one section exists (presumably for the 24-bit section), simply make a copy of that subsection, except on the "Depth" line, put 16 instead of 24.
After that, save your changes and restart X.