To state the obvious: Such an $n$ must naturally have $p\equiv 1 \pmod{12}$ and $q\equiv 1\pmod{4}$. 

Also, it seems that, for each $q$ a prime such that $q^2\vert (1 + p^2), 1 + q^2 + q^4\equiv \epsilon\pmod{p}$, where $p\equiv \epsilon\pmod{4}$ (this holds with or without the $p\equiv 1\pmod{4}$ condition, of course). In this case, we have that $\lceil \sqrt{p}\rceil\leq q\leq p$.

EDIT: Typos galore!