First, you have to make sure all layers are merged into one. Then reduce the color as shown here.
You will be prompted for indexed color settings.
Now save as...
Give it a name and save as bmp. (click the image to see the psp eqivalent screen - notice the options button on the save dialog box).
In photoshop, you're prompted for save options when you save. (click the image to see the psp screen - you get that when you click the options button)
Conversion is successful in both programs.
