Grafx2 coder here. (I played your Doom map as a teen )

A program that handles a real indexed mode internally can let you avoid the problem before it appears... Quite a few exist, free and non-free, unfortunately Photoshop is not one of them.

Now, to fix up an image after the fact:
Load your image Grafx2. If it's 24bit, the program will convert it to indexed mode.
Open the Palette (P key)
The number on the "Reduce" button tells you how many distinct colors are used.

To examine the image:
If you're curious of where the problem pixels happened, hit the "Used" button, it toggles a little white marker on the right side of the colors that your image is actually using.
I recommend "Reduce to - unique" to minimize the palette, then click the "Histo" button to get an idea of which colors are almost unused.
Selecting a range of colors before clicking Histo can help you examine a group of colors.
Clicking a color on the Histo(gram) screen selects it, so you can play with the RGB levels if you want to see which parts of your image are using it.


Reducing colors:
For general color optimization, I'd recommend to eliminate unused colors (Reduce to - uniques), then sort the palette (try either Sort option). Locate two contiguous colors which are suspiciously similar. Select the two of them (click and drag), click Merge, then click "Reduce to uniques". The color count will be reduced by one, as those two colors get completely merged into one, with a RGB value set to a weighted average according to how many pixels were of this color.
Repeat until you don't find any more "duplicates"