The simplest way I found is just to "Borrow" palletes from other units... I do this by taking a similar colored unit, loading it in Flicster, and exporting it as a storyboard with pcx and palletes... Two PSP pallettes are generated automatically (Unit.pal and UnitAlpha.pal)... You want to use the one that does not have the alpha in the pallette name. You can then just apply the pallete to your storyboards, and presto! a properly palletted PCX.
OR if your paint program isn't compatible with JASC Paint Shop Pro Pallettes, just load the PCX into your program, and generate a pallette from that, then import it into the tru color BMP and save it as a PCX.....