http://dervish.tastyspleen.net/files/colormap.zipextract that to your quake2/baseq2 folder.should fix your issueit's some kind of color pallet that comes with the game if you installed a full version from cd. dunno about steam copies.
quadz already suggested this to you, but have you tried this?:http://q2s.tastyspleen.net/There are installers for both Q2PRO and R1Q2, depending on which client you prefer.