There is a way to circumvent this when you use Save for Web though this is a very tedious one, but once it's done, it's worth it (somehow). NOTE: I used CS3 on this tutorial, YMMV.
Making the palette
Choose the frame that has most of the colors then make a palette for that frame using Image>Mode>Indexed Color.
When you're now in the Indexed Color menu, select Local (Perceptual) in Palette, type 256 in Colors and select Custom... in Forced.
Selecting Custom will give you the Forced Colors palette screen, click Load... and select the pal.act in the Data folder. Click OK in all of that and now you got the frame in Indexed mode.
Go to Image>Mode>Color table, this will show the color table screen where you can save your palette to your scene folder or anything convenient (I preferably name the palette file to the name of the scene) and there you have it, the scene palette/act. Now that the easy part is done, the more harder part begins:
Saving the GIF
Save your animated gif via File>Save For Web and Devices. You can see the settings that I have (attached picture), I emphasized the 'Custom' there, since we will now use the scene palette/act that we saved earlier. Don't forget to set the Colors: to 256 and uncheck Transparency and Interlaced.
We then go ahead and choose '>>' which will show a pop up menu, click on Unsorted first, this will now make sure that the palette is not sorted, then go back to '>>' and click Load Color Table... and find your scene palette/act file that we saved earlier, then click Open.
Finally, click on save and save it as the final name of your GIF file, put it on OpenBOR and see that the colors are somewhat preserved. The palette is unjumbled and you can no longer see black spots!
I actually experimented with this beforehand and struggled by it until a moment of clarity came when I realized that the first index color is making the transparency, so I did experimentations and came up with this. Used this on my project's scenes. Hopes this helps people who use Photoshop a lot.
[attachment deleted by admin]