This is not a complete answer, but a reformulation of your question in a way that removes the algebraic number theory, which translates the question into the realm of additive combinatorics. I assume that you also require the order of $a$ in $(\mathbf{Z}/p\mathbf{Z})^*$ to be $h$, as in your examples and Noam's comment. In this case, your conditions are equivalent to the following, where I write $C$ for the subgroup of $(\mathbf{Z}/p\mathbf{Z})^*$ generated by $a$:

- $C$ is a subgroup of $(\mathbf{Z}/p\mathbf{Z})^*$ with $4<\#C<p-1$
- writing $D_1,D_2,\dots,D_r$ for the distinct cosets of $C$ in $(\mathbf{Z}/p\mathbf{Z})^*$, the number of representations of $1$ as a sum $d_1+d_2+\dots+d_r$ with $d_i\in D_i$ differs by $1$ from the number of representations of $0$ as such a sum.

The reason for this is that the constant term of your minimal polynomial is (up to multiplication by $\pm 1$) the norm of your element $x$ from $\mathbf{Q}(\zeta_p)$ to $\mathbf{Q}$. This norm is the product of the conjugates of $x$, and we can write down these conjugates. Let $C$ be the subgroup of $(\mathbf{Z}/p\mathbf{Z})^*$ generated by your element $a$, and let $b_1,\dots,b_r$ (with $r:=(p-1)/h$) be representatives of the distinct cosets of $C$ in $(\mathbf{Z}/p\mathbf{Z})^*$. Then the conjugates of $x$ are the elements
$$
\sum_{k=1}^h \zeta_p^{b_i a^k},
$$
and your question asks when the product of these $(p-1)/h$ numbers is $\pm 1$. Equivalently,
$$
\pm 1 = \prod_{i=1}^r \sum_{c\in C} \zeta_p^{b_i c} = \sum_{c_1,\dots,c_r\in C} \zeta_p^{\sum_{i=1}^r b_i c_i}.
$$
This expression is a $\mathbf{Z}$-linear dependence on the $p$-th roots of unity, so it must have the form $n\cdot 1 + n\cdot\zeta_p+\dots+n\cdot\zeta_p^{p-1}=0$ for some integer $n$. Thus, the collection of sums $\sum_{i=1}^r b_i c_i$ with $c_i\in C$ must consist of $n$ copies of each nonzero element of $\mathbf{Z}/p\mathbf{Z}$, together with either $n-1$ or $n+1$ copies of zero. Finally, any two nonzero elements $u,v$ of $\mathbf{Z}/p\mathbf{Z}$ always have equal numbers of representations as $\sum_{i=1}^r b_i c_i$ with $c_i\in C$, since we get a bijection between the two sets of representations by multiplying all representations of $u$ by $v/u$. Thus your condition is the same as asserting that the numbers of representations of $1$ and $0$ differ by $1$, which is the claimed reformulation.

In view of this reformulation, you might want to add a tag to your question in order to alert the additive combinatorialists, since it seems related to sum-product phenomena.

database for 9T1. $\endgroup$ – Tito Piezas III Oct 27 '13 at 5:00gpcomputation of all $1145$ candidate $(p,h)$ pairs). $\endgroup$ – Noam D. Elkies Oct 27 '13 at 5:36