I have a proof for the following assertion which employs Model Theory. It has certainly a pure group theoretic proof, but what is such a proof? Is the assertion trivial?
Theorem Let $G$ be a finite group and $s\in G$ be an arbitrary element. Suppose $A=C_{\mathrm{Aut}(G)}(s)$. Then $C_G(A)$ is cyclic.
Edition: By the counterexample of Khalid, it seems that the correct statement is following:
Theorem Let $G$ be a finite group and $s\in G$ be an arbitrary element. Suppose $A=C_{\mathrm{Aut}(G)}(s)$. If $C_G(A)$ has odd order then it is cyclic.
Final Edition
In the light of comments and answers, now I can modify my proof and below is the correct form of the Theorem. The proof still applies a result of Model Theory (Svoninius Theorem on definablity of relations) and I will upload the complete proof to ArXiv in the next days. However the old version (which has errors in the proof of the main theorem) will be available in ArXiv today (see http://arxiv.org/abs/1406.7621). Here is the corrected Theorem.
Theorem Let $G$ be a finite group and $s\in G$ be an arbitrary element. Suppose $A=C_{\mathrm{Aut}(G)}(s)$. Then we have $$ C_G(A)\cong (\mathbb{Z}_4^{\ m}\times \mathbb{Z}_{2^e})^{\epsilon}\times \prod_{i=1}^r(\mathbb{Z}_{p_i}^{\ m_i}\times \mathbb{Z}_{p_i^{e_i}}), $$ where
1- $p_i$'s are distinct odd primes and $r\geq 0$.
2- $m$ and $m_i$'s are non-negative integers.
3- $e$ and $e_i$'s are positive integers.
4- $\epsilon=0$ or $1$.
5- if $m\neq 0$ then $e>2$.
6- if $m_i\neq 0$ then $e_i\geq 2$$C_G(A)$ is a direct product of three cyclic groups.
Thank you again for comments and counterexamples.