Ace, I have no idea about what Serif is capable of, but...
When you convert it from 24-bit to 8-bit, look to see if there are any settings or options that allow an "Adaptive" palette conversion. "Adaptive" will look at the colors you actually have in the file, and pick the closest matches. Otherwise, you may be forcing the file to use either a default palette, a System palette, or a Web palette... any of these are no good for what you need. The wording may be different in your program, but should mean the same thing.
Also, if you have an option for "Diffusion Dithering" during the process, use it.
Also also... never reduce the bit-depth of your original master file; always save a copy and change THAT to 8-bit.
Good luck.