After seeing this article, I see that one can in fact easily build a circulant matrix, given its eigenvalues, and vice-versa. (In short: $\mathrm F \mathrm U \mathrm F^\ast$ is always circulant.)
Briefly, given the eigenvalues $u_1,u_2,\dots,u_N$, one simply needs to take the inverse discrete Fourier transform
$a_{1,j}=\frac1{N}\sum_{k=0}^{N-1}u_{k+1}\exp\left(\frac{2\pi i(j-1)k}{N}\right)$
to yield the first row of the circulant matrix $\mathbf A=\mathrm F \mathrm U \mathrm F^\ast$, after which the successive rows of $\mathbf A$ are easily generated. Conversely, the eigenvalues of $\mathbf A$ are generated by taking the DFT of the first row of $\mathbf A$.
Here's a Mathematica demonstration:
n = 100; vec = Sort[RandomReal[{0, 30}, {n}], Greater]; ma = NestList[RotateRight, InverseFourier[vec, FourierParameters -> {1, -1}], n - 1]; Eigenvalues[ma] - vec // Chop