Yup, what Krusty said. Photoshop uses slightly different terms. "Indexed" is 8-bit color.
It won't work if you have layers going on.
The best way to save down to 8-bit in PS:
Save your original "master" file, with all of its layers and effects intact.
Do a "Save as..." and make a copy of the file, in BMP format. Uncheck the "layers" checkbox. Choose 24-bit.
Close the master file.
Open your new, flattened, 24-bit copy.
Change color mode. Image->Mode->Indexed.
Use these exact options...
Palette: Local (adaptive)
Forced: None
Dither: Diffusion
Click Okay, then quit out, save changes.
If you need to alter the skin again, open and work on the master, not the copy you made.
Check out this thread at AH-Skins.com for deeper info.
http://www.ah-skins.com/phpBB2/viewtopic.php?t=38