If you are referring to the color of the legend markers themselves, simply right-click within the Legend area and select Format Legend from the pop-up menu. From there you can change the symbol and color.

If you are dealing with Territories, it's the same kind of thing... right-click and select Territory Colors.