There's probably no "closed form" for any $s>1$. Curiously, though,
the sum can be evaluated for integers $s \leq 0$, in the following sense.
The function $\zeta_{TM}$ extends to an analytic function on
${\bf C} \backslash \{ 1 \}$, with a simple pole at $s=1$
of residue $1/2$, and taking rational values at integers $s \leq 0$,
starting
$\zeta_{TM}(0) = -1/4$,
$\zeta_{TM}(-1) = -1/24$,
$\zeta_{TM}(-2) = 0$,
$\zeta_{TM}(-3) = +1/240$,
and in general
$\zeta_{TM}(s) = \zeta(s) / 2$ for integers $s \leq 0$
(so in particular $\zeta_{TM}$ inherits the "trivial zeros" of $\zeta$ at
$s = -2, -4, -6, \ldots$).
It is more convenient to work with the Dirichlet series whose
$(n+1)^{-s}$ coefficient is $1 - 2 t_n = (-1)^{t_n}$, because
the generating function for $(-1)^{t_n}$, call it
$$
T(z) = \sum_{n=0}^\infty (-1)^{t_n} z^n,
$$
factors as an infinite product:
$$
T(z) = (1-z) (1-z^2) (1-z^4) (1-z^8) \cdots
= \prod_{m=0}^\infty \bigl( 1 - z^{2^m} \bigr).
$$
So define
$$
Z_{TM}(s) = \zeta(s) - 2 \zeta_{TM}(s)
= \sum_{n=0}^\infty \frac{(-1)^{t_n}}{(n+1)^s}.
$$
The usual Mellin-transform trick gives an integral formula:
$$
\Gamma(s) Z_{TM}(s)
= \sum_{n=0}^\infty (-1)^{t_n} \! \int_0^\infty x^{s-1} e^{-(n+1)x} \, dx
= \int_0^\infty x^{s-1} e^{-x} T(e^{-x}) \, dx.
$$
This gives an analytic continuation of $\Gamma(s) Z_{TM}(s)$ to the entire
complex plane, because $T(e^{-x})$ decays faster than any power of $x$
as $x \to 0$: each factor $1 - e^{-2^m x}$ of the infinite product
is $O_m(x)$ and in $(0,1)$. Since $\Gamma(s)$ has no zeros,
but does have simple poles at $s = 0, -1, -2, -3, \ldots$,
it follows that $Z_{TM}$ is an entire function with simple zeros
at the same $s$, and no other real zeros (the integral for
$\Gamma(s) Z_{TM}(s)$ is plainly positive for all real $s$).
Since $Z_{TM} = \zeta - 2 \zeta_{TM}$, we conclude that
$\zeta_{TM}(s) = \frac12 \zeta(s)$ at those $s$, as claimed.
[The integral formula can also be used to compute
$Z_{TM}(s)$, and thus also $\zeta_{TM}(s)$, to high precision;
for example, using gp's "intnum" function we find
$Z_{TM}(2) = 0.6931534522\ldots$ (this is not $\log 2$,
though it's quite close -- the difference is $\lt 10^{-5}$),
so $\zeta_{TM}(2) = (\zeta(2) - Z_{TM}(2)) / 2 = 0.4758903073\ldots$.]
Best Answer
Yes. For $r=0,1$ let $T_r=\{n\in\Bbb N_0: t_n=r\}$. The famous van der Waerden's theorem states that for any partition of the set of natural numbers into finitely many parts there exists a part containing an arbitrary long arithmetic progression. So for each natural number $M$ there exists an arithmetic progression $P$ of length $M$ contained in $T_0$ or $T_1$. Moreover, if $P\subset T_1$ then a set $P’=\{2p+1:p\in P\}$ is an arithmetic progression of length $M$ contained in $T_0$.
Similarly we can show that there is no uniform bound $M$ for the claim from Overview in your answer. Namely, for $0\le r<b-1$ let $T_r=\{n\in\Bbb N_0: t_n=r\}$. By van der Waerden’s theorem, for each number $M$ there exist $0\le r<b-1$ and an arithmetic progression $P$ of length $M$ contained in $T_r$. Pick an arbitrary number $0\le d<b$ coprime to $b-1$ and define a map $f:\Bbb N_0\to \Bbb N_0$ by putting $f(n)=bn+d$ for each $n\in\Bbb N_0$. Then a set $f(P)$ is an arithmetic progression of length $M$ contained in $T_{r’}$, where $r’\equiv r+C_d\pmod {b-1}$. Since $C_d=d^d$ is coprime to $b-1$ too, there exists a natural number $l$ such that $r+C_dl\equiv 0\pmod {b-1}$. Iterating $T$, we obtain that $T^r(P)$ is an arithmetic progression of length $M$ contained in $T_0$.