Follow steps in this answer to create Default.nb in your $UserBaseDirectory
. (replace Package.nb with Default.nb first!)
Then add those style cells:
Cell[StyleData["MessageMenuLabel"], FontColor->RGBColor[0, 0, 1]]
Cell[StyleData["MessageText"], FontColor->RGBColor[1, 0, 1]]
You may need to restart MMA but it should work:

How did I know which styles? Ctrl+Shift+E reveals styles used in messages:
Cell[BoxData[
TemplateBox[{ "Solve","naqs", ...}, "MessageTemplate"]],
"MessagesWindowMessage", "MSG", ShowCellLabel->True, ...
]
And CurrentValue[{StyleDefinitions, "MessageTemplate"}]
reveals DisplayFunction
:
{TemplateBoxOptionsDisplayFunction -> (RowBox[{
TooltipBox[
...,
RowBox[{#1, "::", #2}], BaseStyle -> "MessageMenuLabel"
],
":", " ", StyleBox[#3, "MessageText"]}] &), ...
}