Ok, 128x128 is too small for a texture map. Use 512x512 minimum. 1024x1024 would be better.
8 bit textures means they have only 256 colours. It refers to the colour palette used by the FS engine to render those textures.
So, if you have some texture that you would like to see on a ship, you need to reduce the colour definition to 256 (or 8 bits). It also needs to be a certain size, like 512x512, that´s what "power of 2" means. If you multiply 512x512 by 2, you get 1024x1024. Multiply that by 2 and you get 2048x2048. See the idea? You can´t have, for example, 1060x800, or whatever.
The correct formats are:
2x2
4x4
8x8
16x16
32x32
64x64
128x128
256x256
512x512
... etc etc.
Usually the texture maps are a perfect square, both sides are equal in size. Each of those sets of numbers above refers to a side of the square.
As for your problem, it seems like the FS palette was screwed over. Did you mess with the original map files?