A necessary and sufficient condition is given by the [matroid intersection theorem][1].  Given a (not necessarily properly) edge-colored graph $G=(V,E)$, 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 tree 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, note that $r_1$ and $r_2$ can be specified by oracles that run in polynomial time.  Therefore, by running the matroid intersection algorithm, we can find a total spanning tree (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 spanning tree exists.  To see this, observe that if $T$ is the set of edges of a total spanning tree, 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