As MG_ said, stay away from Colorize setting of a brush. Use this technique instead:
1) Create a new layer and set the blending mode to Color. There are several other blending mode options that will also cause a color-changing effect.
2) A: Choose your color with a normal brush and start painting.
-or- B: Fill the layer with selected color. Then create a mask (filled with black) and paint white in the mask to affect the areas you want to alter.
TIP: Also make sure to work in color modes that give you at least 16-bits per channel. Never work in 8-bit modes unless you are trying to save memory and you are prepared to handle artifacts that often show up when you apply filters, gradients, blends, or other graduated effects.