A necessary and sufficient condition is given by the matroid intersection theorem. 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, 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 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.