Yeah, if the the pallet isn't perfectly following all protocol at the start (Photoshop), then you'll have issues. Even opening it up in Wally and editing the pallet won't work.
What I do:
Change all the colors in the pallet that I want to be pure blue into the same exact color with the same exact values; something like a bright neon green, I then make sure the last color in the pallet is pure blue(0, 0, 255), then I select all the green area with the magic wand tool (make sure anti-aliasing is OFF, and paint over it with the pure blue. Color mode = indexed color ("Perceptual 256 Colors" - er whatever..."Exact" might not always be 256 colors), then save it as an 8-bit .bmp.
This method has appeared to work flawlessly, unless video is set to software mode.
The one problem I ran into was wondering what to do when the most necessary color of the pallet just happened to be the color I needed changed to blue...
Also, textures with a gradient or fade will not work too well, haha.