Solution 1 (by Jon Schneider). Let $A$ be the set of good trees. Consider the operation $S$ which takes a tree, and replaces each edge connecting vertices $x$ and $y$ with an edge connecting vertices $x+1$ and $y+1$ (labels taken modulo $n$). Note that $S$ is invertible and sends good trees to good trees, so it partitions the set $A$ into several orbits (where two trees are in the same orbit if you can reach one from the other by repeatedly applying $S$). We will show that all orbits either have size $n$ or $n/2$, thus proving the required statement.

Given any tree $T$, note that $S^n T = T$ (because $x+n \equiv x \pmod{n}$). Now, if the orbit that $T$ belongs to has size $r$, then $r$ is the smallest positive value satisfying $S^r T = T$, and it follows that $r$ must divide $n$. We now have two cases.

* Case 1 In this case, we assume that $r$ does not divide $n/2$. Consider any edge $(x, y)$ of $T$. Note that if $S^r T = T$, then this implies that the edge $(x+r, y+r)$ is also in $T$, so in particular, the $n/r$ edges
$$(x, y), (x+r, y+r), (x+2r, y+2r), \dots, (x-r, y-r)$$
must belong to $T$. Now, note that all of these edges are distinct; indeed, if the edges $(x, y)$ and $(x + ar, y + ar)$ are the same (for some $1 \le a < \frac{n}{r}$), then the only way this can happen is if (because $x \ne x + ar$)
$$\begin{aligned} x &\equiv y + ar \\ y &\equiv x + ar \end{aligned}$$
But this can only happen if $x \equiv x + 2ar$, or equivalently, $n|2ar$. If $n$ is odd, then this means that $n|ar$, which cannot happen for $1 \le a < \frac{n}{r}$. Likewise, if $n$ is even, because $r$ does not divide $\frac{n}{2}$, this likewise implies that $n|ar$, and again this cannot happen for our choices of $a$. Therefore, we can partition the edges of $T$ into groups of $\frac{n}{r}$ edges. However, $T$ has $n-1$ edges, and $\frac{n}{r}$ cannot divide $n-1$ unless $r=n$, because $\gcd(n-1, n) = 1$. It follows that $r$ must equal $n$, and therefore that the orbit has size $n$.

* Case 2 In this case, we assume that $r$ divides $\frac{n}{2}$ (in particular, $n$ is even). We proceed similarly as in the first case. The only difference this time is that if $y = x + \frac{n}{2}$, then we only have a group of $\frac{n}{2r}$ distinct edges (because in this case, the edges $(x + ar, y + ar)$ are only distinct for $0 \le a < \frac{n}{2r}$). Nonetheless, we can still partition the edges of $T$ into groups of either $\frac{n}{r}$ edges or $\frac{n}{2r}$ edges, which means that $n-1$ must be divisible by $\frac{n}{2r}$. But again, because $\gcd(n-1, n) = 1$, this can only happen if $r = \frac{n}{2}$, and therefore our orbit has size $n/2$.

Solution 2 (by the poser). There are many spanning trees which avoid edges between consecutive labels. Separate them into groups as follows. Given such a labeled spanning tree $T$, consider the tree $T'$ obtained by taking $T$, and replacing each label $i$ with $i+1$, and replacing the label $n$ with $1$. This cycles the labels on the vertices. Say that two trees are of the same type if they can be reached from each other by performing this simple cycling operation some number of times. Importantly, the cycling operation respects the property that no consecutively-labeled vertices span an edge.

Clearly, this completely partitions the spanning trees counted by $T_n$ into some collection of types. It suffices to show that for each fixed type, the number of spanning trees of that type is divisible by $n$ when $n$ is odd, and divisible by $n/2$ when $n$ is even. For this, we will need the following lemma:

Lemma 4. Let $T$ be a tree with vertices labeled $1, \dots, n$, and let $\pi : [n] \to [n]$ be an automorphism of $T$, i.e., where vertices $i$ and $j$ are adjacent in $T$ if and only if $\pi(i)$ and $\pi(j)$ are adjacent in $T$. Then $\pi$ must have a fixed point $\pi(i) = i$ or a fixed edge $\{\pi(i), \pi(j)\} = \{i, j\}$.

Proof. Suppose for contradiction that $\pi$ does not have a fixed point. Then, for every vertex $i$, the permutation $\pi$ maps it to some vertex $\pi(i)$ somewhere else in the tree. Because trees are acyclic and connected, there is a unique path from $i$ to $\pi(i)$, and it departs from $i$ along an edge incident to $i$. Draw an arrow on that edge indicating the direction of departure, and do this for every vertex.

Because there are $n$ vertices and only $n-1$ edges, the pigeonhole principle implies that some edge $\{i, j\}$ receives two arrows. By construction, those two arrows on the same edge must be in different directions, and must indicate that $\pi(i)$ is on the $j$-side of the edge, and $\pi(j)$ is on the $i$-side (according to $T$). Yet because $\pi$ is an automorphism, we must have that $\pi(i)$ and $\pi(j)$ are adjacent in $T$, which therefore implies that $\pi(i) = j$ and $\pi(j) = i$, producing the fixed edge. $\square$

We now apply lemma 4. Consider a particular labeled tree $T$ counted by $T_n$. The number of other trees of the same type is precisely equal to the minimum number of times $k$ that one must apply the cycling operation to $T$ before obtaining $T$ itself again. This corresponds precisely to an automorphism $\pi$ which itself is a cyclic shift $i \mapsto i + k$ (where $n + 1$ corresponds to $1$, etc). It is clear that fixed points do not arise unless $n \mid k$, and fixed edges (transpositions) never arise for odd $n$, immediately proving that $n \mid T_n$ when $n$ is odd.

For even $n$, observe that the only way a cyclic shift can produce a transposition is when $k$ is an odd multiple of $n/2$, because we would need that $i + k + k = i$. Therefore, the period of cycling is either $n/2$ or $n$, but fortunately both are divisible by $n/2$, and so we are done.