Let $A=k^2$ for some $k$. Notice that \[ (A+u)^2 - A = (k^2+u)^2 - k^2 = (k^2-k+u)(k^2+k+u). \]For fixed $n$, take $u$ such that $u\equiv -k^2+k\pmod{n}$ (notice that $k$ is fixed). So, if $A$ is a perfect square, the given property holds. I now prove the opposite direction. Let $A$ not be a perfect square. I will prove the existence of an $n$ such that \[ n\nmid (A+u)^2 - A \]for any $u\in\mathbb{N}$. Since $A$ is not a perfect square, there is a prime $p$ such that $v_p(A) \equiv 1\pmod{2}$. Set $A=p^{2e+1}A'$ where $p\nmid A'$. I show $n=p^{2e+2}$ works. Suppose the contrary that there is an $u_0$ such that \[ p^{2e+2} \mid (A+u_0)^2 - A. \]Clearly $v_p((A+u_0)^2)$ is even, and if $v_p((A+u_0)^2)\le 2e$ then \[ v_p\left((A+u_0)^2 - A\right) = v_p\left((A+u_0)^2\right)\le 2e, \]a contradiction. Likewise, if $v_p((A+u_0)^2)\ge 2e+2$ then \[ v_p\left((A+u_0)^2 - A\right) = v_p(A) =2e+1, \]once again, a contradiction.