The OP has added a lot of conditions to his original statement, so my answer is significantly revised. The OP's statement is still not true. This answer uses ideas from Denis's answer so, if you like this, vote us both up.

Let $A=(B/2)-i(C/2)$, with $B$ and $C$ hermitian. Set $z=x+iy$. We will be interested in the polynomial $$F(x,y) := \det(\mathrm{Id}+zA+\overline{z}A^*) = \det(\mathrm{Id} + x B + y C).$$

By a result of Helton and Vinnikov, given a degree $n$ polynomial $F(x,y)$, there are Hermitian matrices $B$ and $C$ such that $F=\det(\mathrm{Id} + x B + y C)$ if and only if $F(0,0)=1$ and every line through the origin meets $F=0$ at $n$ (real) points. (Vinnikov's paper analyzes the case that $F=\det(xB+yC+D)$, with $D$ positive definite. But, if $D$ is positive definite then we can write $D=SS^*$ and then $\det(S^{-1} B (S^*)^{-1} x + S^{-1} C (S^*)^{-1} C+\mathrm{Id})$ is a scalar multiple of $\det(xB+yC+D)$. So it is easy to relate Vinnikov's formulation to ours.)

I will give polynomials $F$ and thus implicitly give matrices $A$. Making this correspondence explicit is a difficult computational task, so I won't do it. Of course, I need to check that

(Condition 1) Every line through $(0,0)$ meets it at $n$ (real) points, and $F(0,0)=1$.

Now, the OP has imposed the following conditions:

(Condition 2) The matrix $A$ is nilpotent. This is equivalent to $\det(\mathrm{Id}+zA) = 1$. So we want $F \equiv 1 \mod (x-iy)$. Since $F$ is a polynomial with real coefficients, I might as well rewrite this as $F \equiv 1 \mod x^2+y^2$.

(Condition 3) $\det (e^{i \theta} A + e^{-i \theta} A^*)$ is of the form $a + b \cos (n/2) \theta + c \cos n \theta$. Switching to our $x$, $y$ coordinates, when $z=e^{i \theta}$ we have $x=\cos \theta$ and $y = \sin \theta$. So this condition says that $F(\cos \theta, \sin \theta) = a + b \cos (n/2) \theta + c \cos n \theta$. In my example, we will have $F(\cos \theta, \sin \theta) =1$.

The OP asks whether this implies that the eigenvalues of $e^{i \theta} A + e^{-i \theta} A^*$ are independent of $\theta$. These eigenvalues are real numbers, since they are eigenvalues of a Hermitian matrix. We see that $s$ is an eigenvalue if and only if $\det (\mathrm{Id} - s^{-1}(e^{i \theta} A + e^{-i \theta} A^*))=0$ or, in other words, if $F(s^{-1} \cos \theta, s^{-1} \sin \theta)=0$. So these eigenvalues are the reciprocals of the points where a line through the origin meets $F=0$. In short, the question is whether conditions 1, 2 and 3 force $F=0$ to be a union of concentric circles.

And the answer is no. Consider the polynomial $$1-10(x^2+y^2)(x^2+y^2-1)(x^2+2y^2-3)$$

As you can see in the plot below, this is $3$ ovals nested around the origin, so every line through $(0,0)$ meets it $6$ times. The other conditions are obvious. (Note that, although the inner ovals look like circles, they are not; this polynomial is irreducible. In any case, the outer polynomial is clearly not a circle.)

alt text http://www.math.lsa.umich.edu/%7Espeyer/VinPict.png

The OP has added a lot of conditions to his original statement, so my answer is significantly revised. The OP's statement is still not true. This answer uses ideas from Denis's answer so, if you like this, vote us both up.

Let $A=(B/2)-i(C/2)$, with $B$ and $C$ hermitian. Set $z=x+iy$. We will be interested in the polynomial $$F(x,y) := \det(\mathrm{Id}+zA+\overline{z}A^*) = \det(\mathrm{Id} + x B + y C).$$

By a result of Helton and Vinnikov, given a degree $n$ polynomial $F(x,y)$, there are Hermitian matrices $B$ and $C$ such that $F=\det(\mathrm{Id} + x B + y C)$ if and only if $F(0,0)=1$ and every line through the origin meets $F=0$ at $n$ (real) points. (Vinnikov's paper analyzes the case that $F=\det(xB+yC+D)$, with $D$ positive definite. But, if $D$ is positive definite then we can write $D=SS^*$ and then $\det(S^{-1} B (S^*)^{-1} x + S^{-1} C (S^*)^{-1} C+\mathrm{Id})$ is a scalar multiple of $\det(xB+yC+D)$. So it is easy to relate Vinnikov's formulation to ours.)

I will give polynomials $F$ and thus implicitly give matrices $A$. Making this correspondence explicit is a difficult computational task, so I won't do it. Of course, I need to check that

(Condition 1) Every line through $(0,0)$ meets it at $n$ (real) points, and $F(0,0)=1$.

Now, the OP has imposed the following conditions:

(Condition 2) The matrix $A$ is nilpotent. This is equivalent to $\det(\mathrm{Id}+zA) = 1$. So we want $F \equiv 1 \mod (x-iy)$. Since $F$ is a polynomial with real coefficients, I might as well rewrite this as $F \equiv 1 \mod x^2+y^2$.

(Condition 3) $\det (e^{i \theta} A + e^{-i \theta} A^*)$ is of the form $a + b \cos (n/2) \theta + c \cos n \theta$. Switching to our $x$, $y$ coordinates, when $z=e^{i \theta}$ we have $x=\cos \theta$ and $y = \sin \theta$. So this condition says that $F(\cos \theta, \sin \theta) = a + b \cos (n/2) \theta + c \cos n \theta$. In my example, we will have $F(\cos \theta, \sin \theta) =1$.

The OP asks whether this implies that the eigenvalues of $e^{i \theta} A + e^{-i \theta} A^*$ are independent of $\theta$. These eigenvalues are real numbers, since they are eigenvalues of a Hermitian matrix. We see that $s$ is an eigenvalue if and only if $\det (\mathrm{Id} - s^{-1}(e^{i \theta} A + e^{-i \theta} A^*))=0$ or, in other words, if $F(s^{-1} \cos \theta, s^{-1} \sin \theta)=0$. So these eigenvalues are the reciprocals of the points where a line through the origin meets $F=0$. In short, the question is whether conditions 1, 2 and 3 force $F=0$ to be a union of concentric circles.

And the answer is no. Consider the polynomial $$1-10(x^2+y^2)(x^2+y^2-1)(x^2+2y^2-3)$$

As you can see in the plot below, this is $3$ ovals nested around the origin, so every line through $(0,0)$ meets it $6$ times. The other conditions are obvious. (Note that, although the inner ovals look like circles, they are not; this polynomial is irreducible. In any case, the outer polynomial is clearly not a circle.)

      (source)

This is not true. A simple counterexample: $$A = \begin{pmatrix} 0 & 0 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix}$$ $$B = \begin{pmatrix} 0 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}$$

This result is true for $2 \times 2$ matrices, as we will see below.

Here is how I would think about this: Let $F(x,y)$ be the polynomial $\det(\mathrm{Id}+xA+yB)$. The condition that $A$ and $B$ are nilpotent says that $F(0,y)=1$ and $F(x,0)=1$. The condition that the eigenvalues of $A e^{i q} + B e^{-i q}$ are constant says that $F(t e^{iq}, t e^{-iq})$ is constant, in other words, that $F(x,y)$ is a polynomial in $xy$. So you would have a proof if, whenever $F(x,0)=F(0,y)=1$, then $F$ is a polynomial in $xy$. This is true for $\deg F \leq 2$, which proves your result for $2 \times 2$ matrices. But for higher degree $F$ this is very false. For example, look at $F=1+p x^2y+q xy^2+r xy$ for any $(p,q) \neq (0,0)$.

I believe, but cannot immediately cite a reference, that any degree $n$ homogenous polynomial $F(x,y,z)$ can be expressed in the form $\det(xA+yB+zC)$. In any case, I know references which state this for $F$ smooth, and there are plenty of smooth polynomials of the form we need. Moreover, if $F(0,0,1)=1$, then we can replace $(A,B,C)$ by $(A C^{-1}, B C^{-1}, \mathrm{Id})$ in order to take $C=\mathrm{Id}$. So, even if I hadn't found the particular example above, I would already be sure I could find matrices $A$ and $B$ which violated your claim.

The OP has added a lot of conditions to his original statement, so my answer is significantly revised. The OP's statement is still not true. This answer uses ideas from Denis's answer so, if you like this, vote us both up.

Let $A=(B/2)-i(C/2)$, with $B$ and $C$ hermitian. Set $z=x+iy$. We will be interested in the polynomial $$F(x,y) := \det(\mathrm{Id}+zA+\overline{z}A^*) = \det(\mathrm{Id} + x B + y C).$$

By a result of Helton and Vinnikov, given a degree $n$ polynomial $F(x,y)$, there are Hermitian matrices $B$ and $C$ such that $F=\det(\mathrm{Id} + x B + y C)$ if and only if $F(0,0)=1$ and every line through the origin meets $F=0$ at $n$ (real) points. (Vinnikov's paper analyzes the case that $F=\det(xB+yC+D)$, with $D$ positive definite. But, if $D$ is positive definite then we can write $D=SS^*$ and then $\det(S^{-1} B (S^*)^{-1} x + S^{-1} C (S^*)^{-1} C+\mathrm{Id})$ is a scalar multiple of $\det(xB+yC+D)$. So it is easy to relate Vinnikov's formulation to ours.)

I will give polynomials $F$ and thus implicitly give matrices $A$. Making this correspondence explicit is a difficult computational task, so I won't do it. Of course, I need to check that

(Condition 1) Every line through $(0,0)$ meets it at $n$ (real) points, and $F(0,0)=1$.

Now, the OP has imposed the following conditions:

(Condition 2) The matrix $A$ is nilpotent. This is equivalent to $\det(\mathrm{Id}+zA) = 1$. So we want $F \equiv 1 \mod (x-iy)$. Since $F$ is a polynomial with real coefficients, I might as well rewrite this as $F \equiv 1 \mod x^2+y^2$.

(Condition 3) $\det (e^{i \theta} A + e^{-i \theta} A^*)$ is of the form $a + b \cos (n/2) \theta + c \cos n \theta$. Switching to our $x$, $y$ coordinates, when $z=e^{i \theta}$ we have $x=\cos \theta$ and $y = \sin \theta$. So this condition says that $F(\cos \theta, \sin \theta) = a + b \cos (n/2) \theta + c \cos n \theta$. In my example, we will have $F(\cos \theta, \sin \theta) =1$.

The OP asks whether this implies that the eigenvalues of $e^{i \theta} A + e^{-i \theta} A^*$ are independent of $\theta$. These eigenvalues are real numbers, since they are eigenvalues of a Hermitian matrix. We see that $s$ is an eigenvalue if and only if $\det (\mathrm{Id} - s^{-1}(e^{i \theta} A + e^{-i \theta} A^*))=0$ or, in other words, if $F(s^{-1} \cos \theta, s^{-1} \sin \theta)=0$. So these eigenvalues are the reciprocals of the points where a line through the origin meets $F=0$. In short, the question is whether conditions 1, 2 and 3 force $F=0$ to be a union of concentric circles.

And the answer is no. Consider the polynomial $$1-10(x^2+y^2)(x^2+y^2-1)(x^2+2y^2-3)$$

As you can see in the plot below, this is $3$ ovals nested around the origin, so every line through $(0,0)$ meets it $6$ times. The other conditions are obvious. (Note that, although the inner ovals look like circles, they are not; this polynomial is irreducible. In any case, the outer polynomial is clearly not a circle.)

alt text http://www.math.lsa.umich.edu/%7Espeyer/VinPict.png