Let the graph be $G$ and allow multiple edges (but not self-loops, which do nothing anyways). Let the edge colors be red and blue, and let $G_R$ and $G_B$ be the subgraphs formed by the red and blue edges obviously, which the problem tells us have connected components of size at most $n$. Suppose that there are at least as many red components as blue components in the respective subgraphs. By adding new vertices and red edges, enlarge each red component until it contains $n$ vertices, then make it into a $K_n$. Then by adding blue edges (but not new vertices), enlarge each blue component among the "old" vertices (that is, we don't consider the vertices that we just added as their own connected components) until it contains $n$ vertices, then make it into a $K_n$; this is doable since we have at most as many "old" blue components as red components. Finally, form blue $K_n$ with the vertices not yet in any "old" blue components until we can't. The result is that every vertex lies in one of $m$ red $K_n$s, as well as one of $m$ blue $K_n$s. Construct a bipartite graph $T$ on the red and blue components, drawing an edge between two components for each vertex they share (we can have multiple edges between two vertices). It is well-known and easy to prove by Hall's that any regular bipartite graph—possibly with repeated edges—has a perfect matching. Then by repeatedly deleting this perfect matching and inducting down, it actually follows that $T$ has $n$ edge-disjoint perfect matchings, since it's clearly $n$-regular to begin with. Finally, identify each matching with its own color, and color the vertex in $G$ the color of the matching its corresponding edge belongs to. Since no two edges in the same matching share a vertex, no two same-colored vertices share a connected component, so this works. $\blacksquare$

Here's a solution with a very similar idea, but different finishing: Consider the connected components of the graph only with blue edges and number them $a_1, a_2, \dots$ and do the same for the connected components of the graph only formed by the red edges - let them be $b_1, b_2, \dots$. Now consider a bipartite graph with nodes corresponding to the components $a_1, a_2, \dots$ and $b_1, b_2, \dots$. As above, we build between $a_i$ and $b_j$ as many edges as coinciding vertices there are that are in both $a_i$ and $b_j$. Now note that every node is of degree $\leq n$, since every components has $\leq n$ nodes. Hence from Konig's line colouring theorem the graph has an $n$-edge-colouring . Now going back to our original graph, for every node that is both in a blue and in a red component, colour it based on the colour of its corresponding edge in the bipartite graph we considered above. By the properties we imposed, no two nodes in the same connected component will be monochromatic. Now we finally have to deal with the nodes that only in one connected component. In every connected component there are at most $n$ nodes and if $k$ of them have been coloured by now, at most $n-k$ are now left uncoloured and the only condition we have to satisfy is not to have two monochromatic nodes inside this connected component. Since we have exactly $n-k$ colours left, this is possible. Repeat for the rest uncoloured vertices until none remain. $\square$