If someone hands you a prime number $p$, and an algebraic number $x$ inside the HasseWeil bound, is there a normalized newform (say of weight two) so that $a_p=x$, where $a_p$ is the $p$th Fourier coefficient?

Some Remarks. I parse the problem in the following way: Start with a totally real algebraic integer $\alpha$ such that every conjugate of $\alpha$ has absolute value at most $2 \sqrt{p}$. Then does there exist a normalized cuspidal Hecke eigenform $f$ of weight $2$ with $a_p = \alpha$? First, here is a heuristic reason why one should expect this to be false. Suppose we ask a slightly stronger question, namely, that all the coefficients of $f$ are defined over the field $E = \mathbb{Q}(\alpha)$. Then, we are asking for the existence of an abelian variety of $\mathrm{GL}_2$type with endomorphisms by (some order in) the ring $\mathcal{O}_E$. Such objects (ignoring issues of polarization) correspond to rational points on Shimura curves. But these curves, in general, will have large genus, and so there's no reason to expect that they have any rational points. It will probably be hard to prove anything this way, however. A second heuristic is to ask the problem in different weights. For example, is there a weight $12$ normalized cuspidal eigenform $f$ of level coprime to $p$ with $a_p = 0$? This sounds tricky. Maybe Serre even conjectured once that this never happened if $p$ was sufficiently large. Let's say he did. Are you going to contradict Serre? Finally, let me show in a rather cheap way that the answer to the original question is "not always". Suppose that $\alpha = 2 \sqrt{p}$, which satisfies the Weil bounds. Suppose that $a_p = \alpha$, and let $\epsilon$ denote the nebentypus character of $f$. Then the characteristic polynomial of Frobenius is $$x^2  2 \sqrt{p} \cdot x + p \cdot \epsilon(p).$$ I claim that $\epsilon(p)$, which is a root of unity, is actually $1$. (This follows easily from the fact that the roots of this polynomial are Weil numbers and the triangle inequality.) In particular, the characteristic polynomial of Frobenius is actually $$x^2  2 \sqrt{p} \cdot x + p = (x  \sqrt{p})^2.$$ This doesn't happen! Losely speaking, one knows that the action of crystalline Frobenius is semisimple on Abelian varieties, and yet the EichlerShimura relations implies that $(\mathrm{Frob}_p  \sqrt{p})^2 = 0$, which then implies that $\mathrm{Frob}_p = \sqrt{p}$ acts as a scalar, which contradicts how one knows Frobenius to interact with the Hodge Filtration  all this is explained in (and is indeed the main point of) a paper of Coleman and Edixhoven from the groovy 90's. 

