I don't have a complete characterization but I found a counterexample. In the following, we let $\genfrac(){}{0}{m}{n}$ denote the Jacobi symbol.
We proof that:
Let $(u,t)=(17,3)$, then $u$ is not a quadratic residue for $t+un$ for all $n\in \mathbb Z$.
Proof
Since $17\equiv 1 \pmod 4$, by quadratic reciprocity we have
$$
\genfrac(){}{0}{17}{3+(2n)(17)}= 1\cdot \genfrac(){}{0}{3+(2n)(17)}{17}=\genfrac(){}{0}{3}{17}=-1
$$
since $3$ is not a quadratic residue of $17$. This shows that $17$ is not a quadratic residue of the odd subset $3+(2n)(17)$.
It remains to check the remaining even subset $3+(2n+1)(17)=2(10+17n)$. Suppose that $17$ is a quadratic residue for some $n$, so that
$$
a^2 = 17 + k\cdot 2(10+17n)
$$
Then for each odd prime $p$ dividing $10+17n$, we have
$$
a^2 \equiv 17 \pmod p
$$
i.e. $17$ is a quadratic residue of $p$. We first get a classification of such $p$. Using quadratic reciprocity:
$$
\genfrac(){}{0}{p}{17} = 1\cdot \genfrac(){}{0}{17}{p} = 1
$$
since $17$ is a quadratic residue of $p$. Hence $p$ is a quadratic residue of $17$. We know that $3$ is a generator of $(\mathbb Z/17\mathbb Z)^\times$, therefore we can write $p$ as
$$
p \equiv 3^{2e} \pmod{17}
$$
for some integer $e$.
Now suppose the prime factorization of $10+17n$ is
$$
p_1p_2\cdots p_m = 10+17n
$$
Using the fact that $3$ is a generator, we express $p_i$ as
$$
p_i \equiv 3^{e_i} \pmod{17}
$$
Then noting that $10\equiv 3^3 \pmod{17}$, we obtain
$$
\begin{align*}
3^{e_1}3^{e_2} \cdots 3^{e_m} &\equiv 3^3 \pmod{17}\\
e_1+e_2 + \cdots + e_m &\equiv 3 \pmod{\phi(17)=16}
\end{align*}
$$
where $\phi$ is the Euler Totient function. From the last equation, we cannot have all $e_i$ even as the sum would have been even. Therefore there is some $e_j$ that is odd, corresponding to prime $p_j$. Moreover, since $2\equiv 3^{14} \pmod{17}$, $p_j$ must also be odd (to use the reciprocity earlier).
We now have $17$ is a quadratic residue mod an odd $p_j$, which has odd exponent $e_j$. However we have shown earlier that all such odd $p$ must have even exponent $e$, giving us a contradiction.
$$\tag*{$\Box$}$$
We can find infinitely many counter examples of this type, but I have not found other types of counter examples. Perhaps it may be possible to solve the rest of the cases?
