Well, I don't know what the tutorial says, but this is how I do it.
First I render the unit in umteenbazillion colors. This renders out to a series of frames. I use SBB to convert these frames into storyboards.
I look at the storyboards and see if there is one which uses more color. Typically it is the death that uses the most. But, for a human animation it might be one of the attacks.
Then I make a copy of this storyboard (after one incident of accidentically saving over the original). I load this copy.
In photoshop, I click on the IMAGE menu, I select ADJUSTMENTS, I select HUE and Saturation. From this menu, I completely de-saturate the magenta and blue shades. These are already in the palette and are not needed.
Then you change the color of your paint brush to one of the exsiting. (see image below). Just click on the color to change (the back color in the below image is the paint brush). Select some other color you wish to keep that is not black, white, pink nor blue.
Next I change this gray to one of the existing shades in the image. (although this can be done at the end as well, if you go to 161 colors, you will get slightly better results if you do it to begin with). You select the gray shade with the magicwand.
Select the color to remove with the wand (see the icon which is selected)
I suggest you have CONTIGUOUS turned off and the TOLERANCEset to 20 or so.
Next select black and white, they are already in the palette and I do not want them wasting a spot and messing up the dithering. I use the magic wand again to do this.
Once these 3 are selected, I zoom out. Select the paint brush. Make sure it is set to 100% opacity, hard edges and VERY large. Then just paint all the bad colors away.
Up to this point, I have typically been using Photoshop for less than 5 mins.
Your image should now look like crap. But this is a good thing. Since you are not working with THIS image, but with the color palette.
Once this is done, I 2nd check the colors for once I know are in the standard colors and are not needed. If neccessary another round with the magic wand.
Then go to IMAGE menu, select MODE and select indexed colors. I set it to 255 colors.
Now in steps of 10-20 colors I go down to 160 colors (163 if you left gray, black and white in).
First I check the palette. Do I see any shades I do not want. This is much faster than scanning the big 'ole image. To check this I go to IMAGE / MODE / COLOR TABLE.
Cut a few colors, check the table.... repeat.
Once I am at 160 colors, open the color table and take a screen shot of it. I then select NEW image and paste in the screen shot. I move this well out the way and make sure it is visible.
Then I open any PCX file with a Civ3 color palette. I select the 160 colors locations to be imported (see tutorial). I set the First color to WHITE and then highlight all the 160 spots ending at the last color to be replaced and set that one to WHITE. Photoshop will automagically set all the colors in the range to white (or more precisely a graduated spectrum begining at the first color and ending at the last color, but since they are the same...)
I do this so I can clearly see which colors need replacing (ie all the white). I then use the eye dropper to move over the 160 colors I have selected.
Once this is done, I save the PCX file I opened as JUNK.pcx and save the palatte (go to the color table and it allows you to save out the palette).
Then I load up a clean copy of one of my renders, ideally the one I used originally to set the palette.
I use the magic want to make sure all the background pink is indeed pure magenta (255,0,255).
Next, I select the entire storyboard and hit CTRL +C (copy image to buffer).
I then set the image to indexed colors.
I load the palette I saved off. Your image will once again look like crap.
Then, I hit CTRL + V (paste buffer) and magically the image is nice and has your palette all set.
Entire process the first time might take a little time. But, eventually it can be done in less than 10mins. Assuming you are doing a simple unit with a simple palette. A complex palette might require you to manually weed out a few of the colors so you can have better control over the final color list.
Another option to get things done fast is to use the spectrum spread if you know your unit is primarily a single color. For example, a gray ship... you need alot of shades of gray, not super important if they exactly match the pre-existing (rendered) colors.... only that they are well spread out and there is no blue nor pink in them.
Hope this helps, glad to see you branching out.