Let $T \subset E$ be an arbitrary spanning tree on $G$, and let $r$ be an arbitrary vertex to use as the root of $T$. Let's call a coloring quasi-good if it is good except at $r$.
Claim: Given an arbitrary coloring of $E \setminus T$, there is a unique coloring of $G$ that is quasi-good.
Proof: We proceed by induction on the number of edges $T'$ of $T$ not yet colored, with the hypothesis that $T'$ is a subtree of $T$ and for any vertex $v \neq r$, if the partial coloring gives a color to each edge incident to $v$, then the three edges have either distinct or equal colors.
Suppose that $T' \neq \emptyset$, and let $v \neq r$ be a leaf of $T$, with incident edges $e_1,e_2,e_3$ where $e_1 \in T$. If $e_2$ and $e_3$ have the same color, then $e_1$ must have the same color too in any good coloring compatible with the colors given so far. If $e_2$ and $e_3$ have different colors, then $e_1$ must have the third possible color. Hence there is always exactly one way to extend the partial coloring to $e_1$ while staying (partially) good. Finally notice that $T' \setminus \{e_1\}$ is a subtree of $T'$ and $T$. By induction hypothesis we may now color $T'$ and obtain a quasi-good coloring of $G$.
The proof of the claim is somehow similar (but simpler) to an argument made in a beautiful proof of Brooks' theorem by Tamás Fleiner.
When $G$ is bipartite, this procedure actually gives a good coloring (that is, even $r$ is well-colored). Indeed, start from a uniform coloring (each edge has the same color), which is by definition a good coloring. Then for each edge $e \in E \setminus T$, consider $C_e$ the even cycle in $T \cup \{e\}$, and if $e$ does not have the desired color, do $+1$ on each even edge and $-1$ on each odd edge of $C_e$ (choosing the first edge such that after this operation, the color of $e$ is the same as in the partial coloring). One can easily check that modifying a good coloring by alternating along an even cycle gives a good coloring. So in the end we get a good coloring coherent with the partial coloring of $E \setminus T$. Hence the number of good colorings is the same as the number of partial colorings: $3^{|E \setminus T|} = 3^{n/2+1}$.
When $G$ is not bipartite, there must be some edge $e$ with $C_e$ odd. We call such edges odd. If $e$ is an odd edge, instead of considering $C_e$, we may consider the tripod $D_e$ that is the union of the two paths from the extremities of $e$ to $r$. Then given any quasi-good coloring and a tripod $D_e$, one can change by $+1$ or $-1$ the color of each edge on $D_e \cup \{e\}$ and obtain another quasi-good coloring (the $+1$ and $-1$ must be alternating on each path from the center of the tripod to each leaf, and the edges incident to the center must be changed by the same value).
Now let $e$ be an odd edge, and choose an arbitrary coloring of $F := E \setminus T \setminus \{e\}$. Starting from a uniform coloring and using $C_f$ or $D_f \cup \{f\}$ for any $f \in F$, one can get three quasi-good colorings coherent with our partial coloring of $F$, one for each possible color for $e$. A simple case analysis suffices to check that exactly one of these three colorings must be a good-coloring of $G$. This proves that there are as many good colorings of $G$ as the number of partial colorings of $F$, that is $3^{n/2}$.