The decomposition should work if and only if the minimal polynomial of the matrix can be factored into pairwise non-proportional linear factors.

Let me tell you how algebraists think about this (depending on your background, you might find everything here trivial): You have a matrix $S\in\mathrm{M}_n\left(k\right)$, where $k$ is a field. Let $m\in k\left[X\right]$ be the minimal polynomial of $S$. Then, the $k$-algebra $k\left[S\right]$ (this is the $k$-subalgebra of $\mathrm{M}_n\left(k\right)$ generated by $S$) is isomorphic to the $k$-algebra $k\left[X\right] / \left(m\right)$. (Here, $\left(m\right)$ denotes the ideal of $k\left[X\right]$ generated by $m$. As much as I dislike this notation, it is short.)

Now assume that $m$ can be factored into pairwise non-proportional linear factors, i. e. that we have $m=\lambda p_1p_2...p_u$ for some $\lambda\in k$ and some pairwise non-proportional linear polynomials $p_1,p_2,...,p_u$. Then,

$k\left[X\right] / \left(m\right) = k\left[X\right] / \left(p_1p_2...p_u\right)$

$\cong \left(k\left[X\right] / \left(p_1\right)\right) \times \left(k\left[X\right] / \left(p_2\right)\right) \times ... \times \left(k\left[X\right] / \left(p_u\right)\right)$

(where $\times$ means the direct product of $k$-algebras) by the Chinese Remainder Theorem for $k$-algebras. Each $k\left[X\right] / \left(p_i\right)$ is isomorphic to $k$ (because $p_i$ is linear), so that you obtain

$k\left[X\right] / \left(m\right) \cong k \times k \times ... \times k$ (with $u$ times $k$).

Together with $k\left[S\right] \cong k\left[X\right] / \left(m\right)$, this leads to

$k\left[S\right] \cong k \times k \times ... \times k$.

Now, for every $i$, the element $\left(0,0,...,0,1,0,0,...,0\right)$ (with $1$ on the $i$'th place, and $0$ on every other place) of $k \times k \times ... \times k$ corresponds to your $T_i\in k\left[S\right]$ under this isomorphism. Your construction of $T_i$ is pretty much equivalent to the standard constructive proof of the Chinese Remainder Theorem.

On the other hand, if $m$ cannot be factored into pairwise non-proportional linear factors, then $k\left[S\right]$ is not isomorphic to $k \times k \times ... \times k$. However, if $m$ can be factored into linear factors (for example, this happens if $k$ is algebraically closed), then at least it is isomorphic to a direct product of $k$-algebras isomorphic to $k\left[X\right] / \left(X^d\right)$ for various $d$ (each of these $k$-algebras corresponds to a Jordan block of $S$, so you still have elements like $\left(0,0,...,0,1,0,0,...,0\right)$, but they should not be as simple as your $T_i$ anymore, and they do not linearly span that direct product, so you shouldn't expect a formula as simple as $S^k = \sum_i T_i\cdot\left( \text{some constant}\right)^k$ to hold.