Sounds like one of those famous X-configuration problems. You need to look at your xorg.conf file (usually lurking somewhere under /etc directory) and see if it has the correct screen modes. If not, you might have to run xf86config or whatever equivalent is available on Ubuntu. WARNING: configuring X requires extremely intimate knowledge of your hardware; do some research on it first if questions like "vertical refresh rate? 30-50? 40-90? 80-200?" stump you.
My guess here is that the color depth that you've asked for isn't available at the resolution you want. You might get better results from (a) telling it your video card's memory, if it has 4096MB and X only sees it as having 1024MB, for instance, or (b) setting the color depth down if you have it at 24, try it at 16 or so.
Don't feel like the lone ranger: I've easily tried 25 Linux distros in my life and the number one problem I have is getting screen-res/color-depth/video-memory right. My other advice: Pick a live distro that's famous for it's first-rate hardware detection, such as Knoppix. Load up Knoppix, and read the hardware profile in it's KDE info-center menus - you'll have something to go on next time you're helping a less able system detect your hardware.