OK, I think I have a comprehensive answer. Since this is physics-inspired, I'll use bra-ket notation.
First, in my comment above, you can see that if $U_{t_0}$ fixes a subspace $V_n \subset V$, then $U_{t_0}$ is block diagonal:
If we write $U$ in the basis $\{|v_1\rangle,...,|v_N\rangle\}$ and see how it acts on the basis of $V_n$, we must have the lower left block of $U$ be zero. Then, since the columns of unitary matrices form an orthonormal basis of the whole space, the columns of the upper left block of $U$ must be an orthonormal basis of $V_n$ . So, the columns of the right side of $U$ must span ${V_n}^{\perp}$, so that the upper right hand block is zero.
Next, let $W:=U_{t_0}|_{V_n}$ be the upper block of $U_{t_0}$ which acts on $V_n$:
$\quad U_{t_0} = \\left[ \begin{matrix} W & 0 \\\ 0 & W' \end{matrix} \right]$
$W$ is unitary $n \times n$ matrix, and therefore can be diagonalized. Without loss of generality, assume the orthonormal vectors $\{|v_1\rangle,...,|v_n\rangle\}$ diagonalize $W$ with respective eigenvalues $\{\exp(i w_i t_0)\}$. Also, let $\{|h_1\rangle,...,|h_N\rangle\}$ be the orthonormal basis (in general, completely different than the $|v_i\rangle$) which diagonalizes $H$ with eigenvalues $h_j$.
Then, for all $i$ with $1 \le i \le n$,
$\quad \exp(i w_i t_0) = \langle v_i| U_{t_0}|v_i\rangle = \langle v_i|\exp(i H t_0) |v_i\rangle = \sum_{j=1}^N \exp (i h_j t_0) |\langle v_i | h_j \rangle|^2 $.
After multiplying both sides by $\exp(-i w_i t_0) $ we get
$\quad 1 = \sum_{j=1}^N \exp [i (h_j-w_i) t_0] |\langle v_i | h_j \rangle|^2$.
Now, since $\{|h_j\rangle\}$ is an orthonormal basis, the values $|\langle v_i | h_j \rangle|^2$ sum to unity (for fixed, normalized $|v_i\rangle$). That means all the exponentials on the rhs for which $|\langle v_i | h_j \rangle|^2 \neq 0$ must be equal to unity. So,
$\quad (h_j-w_i) \frac{t_0}{2 \pi} \in \mathbb{Z}$
and
$\quad (h_j-h_{j'}) \frac{t_0}{2 \pi} \in \mathbb{Z} \quad \forall j,j'$ such that $\langle v_i | h_j \rangle $ and $ \langle v_i | h_{j'} \rangle \neq 0$.
In other words, for all $|h_j\rangle$ that have non-vanishing inner product with $|v_i\rangle$, the corresponding $h_j$ are separated by integer multiples of $\frac{2 \pi}{t_0}$.
It's easy to show that this is also a sufficient condition. Given $H$ with eigenvalues $h_j$ and any subset $\mathbf{H}_{t_0} \subset \{h_j\}$ such that for all $h_j,h_{j'} \in \mathbf{H}_{t_0}$,
$\quad (h_j-h_{j'}) \frac{t_0}{2 \pi} \in \mathbb{Z}$
then any vector $|v\rangle$ in the span of eigenvectors corresponding to $\mathbf{H}_{t_0}$ will be an eigenvector of $U_{t_0} = \exp(i H t_0)$ with eigenvalue $\exp(i h_j t_0)$ (which is the same for all $h_j \in \mathbf{H}_{t_0}$).
(Everything below is old)
Example (Old)
Still not an answer, but here's a simple but non-trivial example:
Let $U_t$ be the family of unitaries acting on $C^3$ which spatially rotate $R^3$ about the vector $(1,1,0)$ with period $T=2\pi$. Let $t_0 = T/2=\pi$. Then in the standard basis,
$\quad H = \frac{i}{\sqrt{2}}\left[ \begin{matrix} 0 & 0 & 1 \\\ 0 & 0 & -1 \\\ -1 & 1 & 0 \end{matrix} \right] \quad ,$
$\quad U_{t_0/2} = \frac{1}{2}\left[ \begin{matrix} 1 & 1 & -\sqrt{2} \\\ 1 & 1 & \sqrt{2} \\\ \sqrt{2} & -\sqrt{2} & 0 \end{matrix} \right]\quad , \quad U_{t_0} = \left[ \begin{matrix} 0 & 1 & 0 \\\ 1 & 0 & 0 \\\ 0 & 0 & 1 \end{matrix} \right] \quad , \quad U_{T} = I,$
so $U_{t_0}V_2 = V_2$, where $V_2 = \mathrm{span}\{(1,0,0),(0,1,0)\}$. The eigenbasis is $\{(1,-1,-i\sqrt{2}),(1,-1,i\sqrt{2}),(1,1,0)\}$ with respective eigenvalues $\{1,-1,0\}$ for $H$.
Note that $H$ and $U_{t_0 /2}$ are not block diagonal in the standard basis, but $U_{t_0}$ is. In particular, no subset of the eigenvectors of $H$ form an orthonormal basis of $V_2$.
Commutation (Old)
I think the confusion over when you can infer that $H$ is block diagonal comes from the non-uniqueness of matrix roots. Positive matrices have unique positive roots, of course, but unitary matricies do not have unique unitary roots. For example, the $2 \times 2$ identity matrix has itself and
$\quad \left[ \begin{matrix} 0 & 1 \\\ 1 & 0 \end{matrix} \right]$
as square roots, but only the latter mixes the first and second rows. Likewise, I suspect that all non-trivial cases of unitaries fixing subspaces (where non-trivial is defined by Michael Underwood above) will have $t_0$ exactly such that non-degenerate eigenvectors of $H$ are degenerate for $U_{t_0}$.