Update 2017.09.26: As I've just learnt from Tamas Kiraly, this notion is well-studied and has several names, such as k-way cut, k-terminal cut, multiway cut. For at least three colors, the problem becomes $NP$-complete for general graphs, see [E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, and M. Yannakakis: The complexity of multiterminal cuts.][1]

Earlier stuff: For two colors this can be solved in polynomial time for any graph, as it can be converted to a [MinCut problem][2]. Just connect all red vertices into a single vertex $s$, and all blue vertices into another single vertex $t$, obtaining a multigraph (or if you prefer, a graph with edge weights). The Minimum cut in this new graph between $s$ and $t$ gives the partition that gives the coloring maximizing the number of the monochromatic edges.


  [1]: https://pdfs.semanticscholar.org/17ff/d84480267785c6a9987211a8a86a58cea1a9.pdf
  [2]: https://en.wikipedia.org/wiki/Minimum_cut