4 Response updated due to a mistake in discriminant calculation.

I assume $\sqrt{p}$ is not contained in $K$, then the bound you are looking for is available.

Let $\chi$ be the ray class character attached to the quadratic extension $K(\sqrt{p})/K$, then the $L$-function $L(s,\chi)$ has conductor essentially $p$. By a recent result of Venkatesh (Theorem 6.1 in Annals of Math. 172 (2010), 989-1094) we have the subconvex bound $L(s,\chi)\ll |s|^N p^{1/4-1/200}$ on the criticial line $\Re s=1/2$, where $N>0$ is a constant. It follows, by a simple Mellin transformation technique, that for any fixed smooth function $V:(0,\infty)\to\mathbb{C}$ of compact support we have

$$\sum_{\mathfrak{m}\subset\mathcal{O}_K}\chi(\mathfrak{m})V(N\mathfrak{m}/X)\ll p^{1/4-1/200} X^{1/2}.$$

Therefore the absolute value of the left hand side is smaller than $X$ for some $X\gg p^{1/2-1/100}$, where the implied constant depends only on $K$ and $V$. This implies that $\chi$ takes both values $\pm 1$ on prime ideals with norm $\ll p^{1/2-1/100}$.

Perhaps one can complement this with Vinogradov's trick, see Corollary 9.19 in Montgomery-Vaughan: Multiplicative number theory I.

EDIT: As the OP pointed out, all the $p$'s above should be replaced by $p^{(K:\mathbb{Q})}$.

3 Inserted "absolute value" in the text.

I assume $\sqrt{p}$ is not contained in $K$, then the bound you are looking for is available.

Let $\chi$ be the ray class character attached to the quadratic extension $K(\sqrt{p})/K$, then the $L$-function $L(s,\chi)$ has conductor essentially $p$. By a recent result of Venkatesh (Theorem 6.1 in Annals of Math. 172 (2010), 989-1094) we have the subconvex bound $L(s,\chi)\ll |s|^N p^{1/4-1/200}$ on the criticial line $\Re s=1/2$, where $N>0$ is a constant. It follows, by a simple Mellin transformation technique, that for any fixed smooth function $V:(0,\infty)\to\mathbb{C}$ of compact support we have

$$\sum_{\mathfrak{m}\subset\mathcal{O}_K}\chi(\mathfrak{m})V(N\mathfrak{m}/X)\ll p^{1/4-1/200} X^{1/2}.$$

Therefore the absolute value of the left hand side is smaller than $X$ for some $X\gg p^{1/2-1/100}$, where the implied constant depends only on $K$ and $V$. This implies that $\chi$ takes both values $\pm 1$ on prime ideals with norm $\ll p^{1/2-1/100}$.

Perhaps one can complement this with Vinogradov's trick, see Corollary 9.19 in Montgomery-Vaughan: Multiplicative number theory I.

2 I improved some of the exponents as I was overly cautious.

I assume $\sqrt{p}$ is not contained in $K$, then the bound you are looking for is available.

Let $\chi$ be the ray class character attached to the quadratic extension $K(\sqrt{p})/K$, then the $L$-function $L(s,\chi)$ has conductor essentially $p$. By a recent result of Venkatesh (Theorem 6.1 in Annals of Math. 172 (2010), 989-1094) we have the subconvex bound $L(s,\chi)\ll |s|^N p^{1/4-1/200}$ on the criticial line $\Re s=1/2$, where $N>0$ is a constant. It follows, by a simple Mellin transformation technique, that for any fixed smooth function $V:(0,\infty)\to\mathbb{C}$ of compact support we have

$$\sum_{\mathfrak{m}\subset\mathcal{O}_K}\chi(\mathfrak{m})V(N\mathfrak{m}/X)\ll p^{1/4-1/200} X^{1/2+1/10000},$$

say. X^{1/2}.

Therefore the left hand side is smaller than $X$ for some $X\gg p^{1/2-1/200}$p^{1/2-1/100}$, where the implied constant depends only on$K$and$V$. This implies that$\chi$takes both values$\pm 1$on prime ideals with norm$\ll p^{1/2-1/200}$p^{1/2-1/100}$.

Perhaps one can complement this with Vinogradov's trick, see Corollary 9.19 in Montgomery-Vaughan: Multiplicative number theory I.

1