Sometimes (for whatever reason) Windows will only list a limited set of colours for you to choose even though your GFX Card/drivers/monitor etc maybe able to display many more. Happened to me when I installed DX 2 on an ol Win95 PC.
Try the following (I'll assume you have the lastest SP and drivers installed for the GFX card OS & monitor):
On the settings tab of the display properties dialog choose 'List all modes' button. Choose the mode that you want, click 'test' and if all is well 'ok'.
If that doesn't work then (start->run->regedit) HKEY_CURRENT_CONFIG\System\CurrentControlSet\Services\...
You should then see 2 subkeys here: VGASave (the system default vga driver) and another relating to your GFX card (on my system this is called promnt), if your not sure look in your '\System32\Drivers' folder as the subkey shares the same name as your GFX card driver.
Now highlight the key that corrisponds to your video driver and then the Device0 subkey now edit the following DWORD value in the right hand pane:
'DefaultSettings.BitsPerPixel' change this to a decimal value of 8 for 256 colours or 16 for 16bit 'High Colour' and so on.
You can also set your screen resolution and refresh rate here, the DWORD values should be pretty self explanatory.
Hope this helps somewhat