"Flipping" a circulant matrix in the time dimensional sense:
$$\left[\begin{array}{ccc}1&16&4\\4&1&16\\16&4&1\end{array}\right] \to \left[\begin{array}{ccc}4&16&1\\16&1&4\\1&4&16\end{array}\right]$$
breaks the eigensystem so that it is no longer sure to be the complex exponentials. But indeed if we look at the power spectrum of the rows of $\bf V, M=VDV^T, VV^T=I$ some random such matrix $\bf M$, we do indeed get a very clear symmetry with all power distinctly spread symmetrically around the 0 frequency, seemingly atomic:
In the time domain the first four rows of $\bf V$ look like this:
And we can see a clear periodic pattern of different frequencies, although not perfect Fourier basis functions.
Peculiarly, all of them also seem to be real valued, and the eigenvalues as well! This makes me suspect they could be related to the Fourier transform basis functions. Something like it's annoyingly suspiciously well behaved twin or something.
Can we derive some expression for those functions?
Consider the $n\times n$ matrices $X,Y$ where $X_{k,n+1-k}=1$, $Y_{k,k+1}=1$, $Y_{n,1}=1$ and other entries are zero. The usual circulant matrix is of the form $$ C=\sum_{k=0}^{n-1}c_iY^k $$ while your matrix is of the form $$ M=\sum_{k=0}^{n-1}XY^k. $$ Note that $X^2=Y^n=I$ and $YXY=X$, so these matrices form a representation of the dihedral group of order $2n$. This group has only 1 and 2 dimensional irreducible representations (over $\mathbb C$), so we should be able to split $\mathbb C^n$ into vector spaces of dimension at most $2$ which are invariant under $X$ and $Y$ (and therefore $M$). Explicitly, let $\omega=e^{2\pi i/n}$ and $$ v_k=(1,\omega^k,\omega^{2k},\ldots,\omega^{(n-1)k})^T. $$ Then $v_0,\ldots,v_{n-1}$ form an eigenbasis for $Y$, with $Yv_k=\omega^k v_k$. Note that $v_k$ is also an eigenvector of $C$ with eigenvalue $$ z_k=\sum_{l=0}^nc_l\omega^{kl}. $$ The identity $YXY=X$ implies that $X$ must permute the eignenspaces of $Y$, and indeed $$ Xv_k=\omega^{-k}v_{-k} $$ (note $v_{-k}=v_{n-k}$). Thus for $0<k<n/2$, the vectors $B_k=(v_k,\omega^{(n-1)k}v_{-k})$ form a basis for a $2$-dimensional subspace on which $X$ and $Y$ act as $$ [X]_{B_k}=\begin{bmatrix}0&1\\1&0\end{bmatrix},\, [Y]_{B_k}=\begin{bmatrix}\omega^k&0\\0&\omega^{-k}\end{bmatrix}. $$ Assuming the $c_i$ are real, the action of $M$ on this subspace is $$ [M]_{B_k}=\begin{bmatrix}0&\bar z_k\\z_k&0\end{bmatrix}. $$ This above matrix has trace $0$ and determinant $-|z_k|^2$, so its eigenvalues are $\pm|z_k|$.
$X$ and $Y$ both fix $v_0$. Finally if $n$ is even, $X$ and $Y$ both act as $-1$ on $v_{n/2}$. Therefore the eigenvalues and eigenvectors of $M$ are $$\begin{array}{lll} \pm|z_k|,&|z_k|v_k\pm z_k\omega^{-k}v_{-k}&\text{ for }0<k<n/2,\\ z_0,&v_0,\\ -z_{n/2},&v_{n/2}&\text{ if }n\text{ is even} \end{array}$$