Photoshop :: "color Replacing" An Index Colored Image

I'm using Adobe Photoshop 9.0 cs2 and I need help with a large color replacement project. I'm an amature video game designer making a level for the classic P.C. game Doom 2 and I'm creating a new weapon and monster for the level I'm creating. For the monster I plan to alter the colors of the frames of the original monster and change the dimensions of key features.

use an indexed color mode that were extracted into individual .png files.

Today I made the big mistake of changing the frames over to RGB mode so I can use the color replacement tools available in that mode. I should have done one frame first then convert it back to indexed color mode because the frames look terrible when converted back from RGB mode. What it is doing is using all the colors of the RGB color spectrum to replace various colors. Unfortunately what this means is that its using colors that are not in the color palette I loaded in the original pic and when I convert it back it looks terrible. There are enough colors in the doom color palette to produce the look I'm after but the automated conversion process from RGB to indexed colors does not pic the best matches in most cases. By doing this I am taking an image consisting of about 150 different shades of color down to about 75 different shades of color. I cant find any color replacement tools for indexed colored images and its going to take me forever to do all frames pixel by pixel so I need one of two things to be able to accomplish what I need. Either a better way of converting these images back, or some tool I can actually use in indexed color mode. If there is a way to select a pixel and change all other pixels of that exact color to a new color then I can just do it pixel by pixel that way. I need something here or I'm going to lose hours of work. If there is a way to load my color table into RGB mode to limit what colors it uses that might work too.

I would just leave the pics in RGB mode if the game im editing for could use that format but unfortunatly anything I convert to RGB will have to be converted back to 256 colors for it to work in the game.