The argument that follows is probably a variant of what Qiaochu Yuan had in mind. We will use the compact notation $(a/b)$ for the Jacobi symbol.
It is clear that $n=3$ does not work. A natural candidate for $n>3$ is $m=4$. Since it is a perfect square, it does the job unless $3$ divides $n$. So if $n>1$ and $3$ does not divide $n$, there is a simple $m$ with the desired property. So from now on we only consider $n$ that are divisible by $3$.
Let $3^k$ be the greatest power of $3$ that divides $n$. Suppose that $k$ is odd, and $n=3^kq^2$. Our $m$ must be congruent to $2$ modulo $3$. Thus $(m/3^k)=-1$, and therefore $(m/q^2)=1$, for any $m$ relatively prime to $q$. It follows that in this case there is no $m$ that works. We will show that in all other cases, there is an $m$ that works.
Look first at the case $n=3^kq$, where $3^k$ is the largest power of $3$ that divides $n$, $k$ is even, and $q \ne 1$. Choose $m \equiv 2 \pmod{3}$, and $m \equiv 4 \pmod{q}$. There is such an $m$ with $1 by the Chinese Remainder Theorem. It is easy to see that $m$ and $m-1$ are relatively prime to $n$, and that $(m/n)=1$. If $q=1$ the situation is even easier.
So now we deal with $n=3^kq$, where $(3,q)=1$, $k$ is odd, and $q$ is not a perfect square. Let $m \equiv 2 \pmod{3}$. Then $(m/3^k)=-1$. Let $p$ be a prime that divides $q$ to an odd power (there is such a $p$ since $q$ is not a perfect square). Choose any quadratic non-residue $a$ of $p$. Let $q=p^s r$, where $r$ is not divisible by $p$. If $r=1$, use the Chinese Remainder Theorem to produce $m$ in the right range congruent to $2$ modulo $3$ and to $a$ modulo $p$. If $r \ne 1$, use the Chinese Remainder Theorem to produce an $m$ in the right range with $m$ congruent to $2$ modulo $3$, to $a$ modulo $p$, and to $4$ modulo $r$. Then $(m/n)=1$ and $m-1$ is relatively prime to $n$, so we are finished.