Not sure what video card you have, but it sounds like the video card may not have enough memory to run or the video card driver is not able to initialize the card for the settings chosen.
Try setting the resolution to 640x480 and use 16 bit color and see what happens.
Also try running DXDIAG and get the video card information from it and post it here, if that fails.