Let $C$ be an $n \times n$ circulant matrix, with first column $ c = (c_1, \dots, c_n)^T$. Let $D$ be its inverse. Since $C$ is circulant, so is its inverse, so $D$ is circulant. Let $D$'s first column be $d = (d_1, \dots, d_n)^T$.
If we know the whole first column $d$ of $D$, we know the whole of $D$, so it is enough to solve the system
$$Cd = \begin{pmatrix} 1 \\ 0 \\ \vdots \\ 0 \end{pmatrix}$$
to find $d$ and through that find $D$. Solving linear systems with a circulant matrix can be done quite fast, $O(n \log n)$, as described on the Wikipedia page for circulant matrices.
If $C$ is also symmetric, the inverse $D$ will also be symmetric. $C$'s first column will be $c = (c_0, c_1, c_2, \dots, c_i, c_{i-1}, \dots, c_1)^T$ with $i = \lfloor i /2 \rfloor$ and one $c_i$ "in the middle" of $c$ if $n$ is even, two if $n$ is odd.
This goes for the inverse, $D$ as well. So in the system $Cd = e_1$ some variables will be the same in $d$, which is a bit of a hassle. You could just solve it anyway, then make sure that your solution $d$ is correct (e.g. the second element is the same as the last element, etc. Maybe it always will be correct, I do not know).
But we can alter the matrix $C$ and the vector $d$ to get a smaller, nicer system. We cut down $d$ to half: $\tilde d = (c_0, c_1, \dots, c_i)^T$ and "fold" $C$ on itself. The folding of $C$ has to be done differently depending on if $n$ is even or odd.
For example, for $n = 4$ we transform:
$$
C =
\begin{pmatrix}
c_0 & c_1 & c_2 & c_1 \\
c_1 & c_0 & c_1 & c_2 \\
c_2 & c_1 & c_0 & c_1 \\
c_1 & c_2 & c_1 & c_0
\end{pmatrix}
\to
\begin{pmatrix}
c_0 & c_1 + c_1 & c_2 \\
c_1 & c_0 + c_2 & c_1 \\
c_2 & c_1 + c_1 & c_0 \\
\end{pmatrix}
= \tilde C
$$
where the fourth column has been added to the second and the fourth row has been removed (it would be the same as the second row). For $n = 5$:
$$
C =
\begin{pmatrix}
c_0 & c_1 & c_2 & c_2 & c_1\\
c_1 & c_0 & c_1 & c_2 & c_2\\
c_2 & c_1 & c_0 & c_1 & c_2\\
c_2 & c_2 & c_1 & c_0 & c_1\\
c_1 & c_2 & c_2 & c_1 & c_0
\end{pmatrix}
\to
\begin{pmatrix}
c_0 & c_1 + c_1 & c_2 + c_2 \\
c_1 & c_0 + c_2 & c_1 + c_2 \\
c_2 & c_1 + c_2 & c_0 + c_1 \\
\end{pmatrix}
= \tilde C
$$
where the fourth column has been added to the third column, the fifth column has been added to the second and the fourth and fifth row has been discarded.
So the difference between if $n$ is odd or even is if something is added to the last row in $\tilde C$.
You can the solve the system $\tilde C \tilde d = e_1$. Note that this system is no longer circulant, so you can not solve it in $O(\frac{n}{2} \log \frac{n}{2})$, but instead $O(\frac{n^3}{2^3})$ so if the solution for circulant matrices works fine, I would probably go with that.
Best Answer
It is enough to prove this: for any invertible square matrix $A$, we have $$(\mkern1mu{}^{\mathrm t\!}A)^{-1}={}^{\mathrm t\mkern-1.5mu}(A^{-1}) $$
Indeed $$^{\mathrm t\mkern-1.5mu}(A^{-1}){\,}^{\mathrm t\!}A={}^{\mathrm t\mkern-2mu}(A\,A^{-1})={}^{\mathrm t\mkern-1.5mu}I=I,$$ and similarly $$^{\mathrm t\!}A{\,}^{\mathrm t\mkern-1.5mu}(A^{-1})={}^{\mathrm t\mkern-1.5mu}(A^{-1}A)={}^{\mathrm t\mkern-1.5mu}I=I.$$ In particular, if $A$ is symmetric, $\;\mkern1mu{}^{\mathrm t\!}A=A$, so $$A^{-1}={}^{\mathrm t\mkern-1.5mu}(A^{-1}), $$ which means $A^{-1}$ is symmetric.