If you do not care about connectedness, then a necessary and sufficient condition is given by the [matroid intersection theorem][1]. Let $G=(V,E)$ be a (not necessarily properly) edge-colored graph.  Define a *total forest* to be the set of edges of a forest which contains every colour exactly once.   

Let $M_1$ be the matroid with ground set $E$, where a set is independent if and only if it contains at most one edge of each colour.  Let $M_2$ be the matroid with ground set $E$ where a set is independent if and only if it does not contain a cycle.  Let $r_1$ and $r_2$ be the rank functions of $M_1$ and $M_2$, and let $t$ be the total number of colours.  Observe that a total rainbow forest exists if and only if $M_1$ and $M_2$ have a common independent set of size $t$.  By the matroid intersection theorem this is true if and only if for all $A \subseteq E$,

$r_1(A) + r_2(E \setminus A) \geq t$.  

Moreover, it is clear that independence testing for $M_1$ and $M_2$ can both be done in polynomial-time. Therefore, by running the matroid intersection algorithm, we can find a total forest (if it exists) in polynomial-time, or a set $A \subseteq E$ such that 

$r_1(A) + r_2(E \setminus A) < t$.  

Note that such a set $A$ certifies that no total forest exists.  To see this, observe that if $T$ is the set of edges of a total forest, then

$t=|T|=|T \cap A| +|T \cap (E \setminus A)| \leq r_1(A)+r_2(E \setminus A) < t$, 

which is a contradiction.  


  [1]: https://en.wikipedia.org/wiki/Matroid_intersection