Are you using the File > Export path to save your work?
If so try using File > Image Preview. On the left of the dialog window under Option (CS5) you can select GIF and set the number of colors to 256 and see what you are going to get before saving / exporting it.
Yes, I did all of that. And after numerous hours and headaches I just gave up on Fireworks and used Photoshop instead.
Thank you for replying but I probably won't use Fw again. At least not for this