A double centralizing theorem for finite groups 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 $C_G(A)$ is a direct product of three cyclic groups.
Thank you again for comments and counterexamples. 
 A: Following the remarks at the end of Khalid Bou-Rabee's answer,I think there will be counterexamples when $p$ is odd. Here's a general strategy to construct them, following pretty much what happens when $p =2$ in that answer. Assume now that $p$ is odd.
It is known that almost all $p$-groups have automorphism group a $p$-group (with an appropriate measure). Take a finite $p$-group $G$ of class $2$ such that $X = {\rm Aut}(G)$ is a $p$-group (we do need $\Omega_{1}(G) \not \leq Z(G).$ Since $G$ has class $2$ and $p$ is odd, this is equivalent to $G$ containing a non-central element of order $p$).
Then $C_{G}(X)$ meets $Z(G)$ non-trivially. Let $z$ be an element of order $p$ in $C_{G}(X) \cap Z(P)$. Now $G$ contain a non-central element $s$ of order of order $p.$ Setting $A = C_{X}(s),$ we see that $\langle z,s \rangle \leq C_{G}(A),$ so that the latter group is not cyclic.
A: Here is an expanded version of my comment (it turns out you don't need the generalized Heisenberg group, just the standard one). My claim is that the theorem as stated is false.
Consider the Heisenberg group, $H$, defined over $\mathbb{Z}/2$. This finite group may be described simply as upper triangular matrices in $SL_3(\mathbb{Z}/2\mathbb{Z})$ with ones along the diagonal.
Let $b$ be the elementary matrix 
$$
\begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}.
$$
As Johannes Hahn suggested, the group $A := C_{Aut(H)}(b)$ is defined to be all the automorphisms of $H$ that fix $b$. Given Marty Isaacs comment, $C_H(A)$ is defined by:
$$
C_H(A) := \{ g \in H : \forall a \in A, a(g) = g \}.
$$
However, if $\phi : H \to H$ is any automorphism, then $\forall a, b \in H$, we have $\phi([a,b]) = [\phi(a), \phi(b)]$. Thus, if $a$ and $b$ commute, then their images commute. As $\phi$ is surjective it follows that $\phi(Z(H)) \leq Z(H)$. Since $Z(H) = \mathbb{Z}/2 \mathbb{Z}$ and since $\phi$ is injective: $\phi(Z(H)) = Z(H)$. Thus, $\phi$ must fix the element, call it $c$, that generates the center of $H$.
By definition of $A$, for any $a \in A$ we have $a(b) = b$. Further, by the previous paragraph, $\forall a \in A, a(c) = c$. Thus $C_H(A)$ contains $\left< b, c \right>$ which is precisely $\mathbb{Z}/2 \times \mathbb{Z}/2$. This is not cyclic, so the theorem stated in this question does not hold for all finite groups.
Final remarks.
There seems to be something special about two here. Maybe the theorem is true if your finite group has order that is not divisible by two? Or perhaps you have a different definition of $C_G(A)$ in mind?
Update: Geoff Robinson's answer shows that there is nothing special about two here.
