Edited answer (see below for my original, less useful reply): Since your polynomial p(z) of degree 2d is palindromic, rewrite it as z^d q(z+1/z) for some polynomial q(x) of degree d. Then p(z) has 2d roots on the circle if and only if q(x) has d real roots in the interval [-2,2]. (Equivalently, q(x-2) should have d nonnegative real roots, while q(x+2) should have no positive roots.) Now you can try to extract information using e.g. Sturm sequences to try to count real roots in that interval.
I had previously posted: Since the real line parameterizes the circle (minus a point), you can transform your problem into counting the real zeros of an associated real polynomial. (See p. 182 of Rodriguez Villegas's book "Experimental Number Theory" for details; this is viewable in Google Books.)
There certainly have to exist necessary & sufficient criteria for all the zeros of a real polynomial to be real, involving rather complicated inequalities in the coefficients of the polynomial, generalizing the condition b^2-4ac >= 0 for quadratics; or for a specific polynomial you can try a real-root-counting algorithm (see Sturm's theorem on Wikipedia). For rather easier sufficient (but not necessary) conditions, you might get lucky and the real roots might be countable by Descartes's rule of signs.
