  We study sign changes in the sequence $\{ A(n) : n = c^2 + d^2 \}$, where
$A(n)$ are the coefficients of a holomorphic cuspidal Hecke eigenform. After
proving a variant of an axiomatization for detecting and quantifying sign
changes introduced by Meher and Murty, we show that there are at least
$X^{\frac{1}{4} - \epsilon}$ sign changes in each interval $[X, 2X]$ for $X \gg
1$. This improves to $X^{\frac{1}{2} - \epsilon}$ many sign changes assuming
the Generalized Lindel\"{o}f Hypothesis.
