I followed the link in the question, and the reduction there actually produces graphs whose edges have a natural coloring such that each $K_n$ present in the graph is a "rainbow $K_n$" (has exactly one edge of each color). In other words, we can easily adjust the reduction in that paper so that it reduces to your problem instead of reducing to the partition into $K_n$s problem: simply assign each edge a color according to this natural coloring and then the graph can be partitioned into "rainbow $K_n$s" if and only if it could be partitioned into $K_n$s at all.
The basic structure of the reduction in that paper can be accomplished with the following 3 steps:
- Create many copies of a particular graph $H_{n,p}$.
- Identify certain pieces of some copies of $H_{n,p}$ with each other (i.e. merge vertices/edges between multiple different copies of $H_{n,p}$).
- Remove certain vertices/edges from some copies.
The graph $H_{n,p}$ has as its vertices the set of length-$n$ vectors modulo $p$ for which the components add to $0$ mod $p$. The edges connect every two vertices that differ in only two components with differences of $+1$ and $-1$ in those two components.
I propose the following coloring for this graph: assign a color to each edge according to its direction. If $x$ and $y$ are adjacent vertices, then $x-y$ is a vector with $n-2$ components equal to $0$, one component equal to $1$ and one component equal to $-1$. In other words, for every edge $(x, y)$ there are ${n \choose 2}$ options for which components of $x-y$ are non-zero. If we assign a unique color to each of these options then we have a coloring for all the edges such that every edge in the same direction has the same color. It is pretty easy to verify that no two edges in a $K_n$ in $H_{n,p}$ are in the same direction. Therefore every $K_n$ in $H_{n,p}$ is a rainbow $K_n$ under this coloring.
When we follow the reduction, we use this coloring for every copy of $H_{n,p}$. Therefore at the end of step 1 in the list above, every $K_n$ in the graph is a rainbow $K_n$.
In step 2 of the above list, we identify some vertices/edges with each other. In particular, in the reduction we always identify a $K_n$ with another $K_n$. But in this situation (where all the $K_n$s are from a copy of $H_{n,p}$), every $K_n$ is either a translation of the "standard $K_n$" which the paper calls $K$ or a translation of $-K$. Therefore, we are either identifying two parallel $K_n$s or two $K_n$s that are "flips" of each other. In either case, the edges that are identified across the two $K_n$s are parallel and are therefore the same color. For example, see Figure 2 in the paper; edges that are identified are always parallel. Thus, since we never try to identify two edges of different colors, the coloring at the end of step 1 in the above list can be naturally extended into a coloring at the end of step 2. Identifying certain vertices/edges together doesn't create any new $K_n$s, so it is still the case at the end of this step that every $K_n$ is a rainbow $K_n$.
Finally in step 3 we remove some vertices/edges, which also doesn't create any new $K_n$s. Thus, we have our desired property: under the coloring I provided, every $K_n$ in the graph generated by this reduction is a rainbow $K_n$.
