no, do not use 256.
the last 32 colours are fullbright. (in both images, that's the bottom couple of rows)

also, sock, i found when i was creating q1 editor textures that first shrinking 50% with bi-cubic or some interpolating algorithm, THEN shrinking with a nearest algorithm yielded better results than just shrinking 25% with interpolation.
the final reduction with nearest will give harder edges otherwise it looks a little blurred out.

finally, i'd recommend not converting all the different coloured textures together. esp. the green and blue ones would benefit from some heavy dithering while the concrete ones would probably be better off with none or very light dithering.

you might want to convert the layers separately in the case of concrete + metal overlay textures.

just my 0.02 anyway.