Alternative proof that $U(n^2-1)$ is not cyclic for $n>2$.

Using Theorem 4.4, one sees that if $2$ divides $\phi(n^2-1)$ (which is the order of $U(n^2-1)$, an even number) and this group is cyclic then there must be exactly $\phi(2) = 1$ elements of order 2.

The order of $n^2-2$ is $2$ (it is congruent to -1 modulo $n^2-1$) and the order of $n$ is clearly $2$ as well. This contradicts Theorem 4.4 if we assume that the group is cyclic.

Your second approach is right on: if $a=\pm 1, \pm n$, then $a^2 \equiv 1 \bmod n^2-1$.

The argument relies on this fact:

If $G$ is a cyclic group of order $m$ and $d$ divides $m$, then there is exactly one subgroup of $G$ of order $d$; it is the set of solutions of $x^d=1$.

For a proof, see here.