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.
curves adjustment
on it and it definitely seems like the red side has sort of circular brush marks, whereas the blue side is smoother. In general terms; If you want to recolor the whole thing, useLayer > New adjustment layer > Hue/Saturation...