If the automorphism group is cyclic, then the Inner automorphism group is cyclic. But the inner automorphism group is isomorphic to $G/Z(G)$, and if $G/Z(G)$ is cyclic, then it is trivial. Therefore, $G=Z(G)$ so $G$ is abelian. (The argument does not require $G$ to be finite, by the by.)
For the latter:
Prop. If $H\subseteq Z(G)$ and $G/H$ is cyclic, then $G$ is abelian.
Suppose $G/H$ is cyclic, with $H\subseteq Z(G)$. Let $g\in G$ be such that $gH$ generates $G/H$. Then every $x\in G$ can be written as $x=g^kh$ for some integer $k$ and some $h\in H$. Given $x,y\in G$, we have $x=g^kh$ and $y=g^{\ell}h'$, so
$$\begin{align*}
xy &= (g^kh)(g^{\ell}h')\\
&= g^kg^{\ell}hh' &\quad&\text{since }h\in Z(G)\\
&= g^{\ell}g^kh'h\\
&= g^{\ell}h'g^kh &&\text{since }h'\in Z(G)\\
&= (g^{\ell}h')(g^kh)\\
&= yx,
\end{align*}$$
hence $G$ is abelian. QED
For more on what groups can occur as central quotients, see this previous question.
Added. Since you mention you did not know that $\mathrm{Inn}(G)\cong G/Z(G)$, let's do that too:
Define a map $G\to \mathrm{Aut}(G)$ by mapping $g\mapsto \varphi_g$, where $\varphi_g$ is "conjugation by $g$". That is, for all $x\in G$,
$\varphi_g(x) = gxg^{-1}$.
This map is a group homomorphism: if $g,h\in G$, then we want to show that $\varphi_{gh} = \varphi_g\circ\varphi_h$. To that end, let $x\in G$ be any element, and we show that $\varphi_{gh}(x) = \varphi_g(\varphi_h(x))$.
$$\varphi_{gh}(x) = (gh)x(gh)^{-1} = ghxh^{-1}g^{-1}= g(hxh^{-1})g^{-1} = \varphi_g(hxh^{-1}) = \varphi_g(\varphi_h(x)).$$
Therefore, the map $g\mapsto\varphi_g$ is a homomorphism from $G$ onto $\mathrm{Inn}(G)$. By the Isomorphism Theorem, $\mathrm{Inn}(G)$ is isomorphic to $G/N$, where $N$ is the kernel of this homomorphism.
What is $N$? $g\in N$ if and only if $\varphi_g$ is the identity element of $\mathrm{Aut}(G)$, which is the identity; that is, if and only if $\varphi_g(x)=x$ for all $x\in G$. But $\varphi_g(x)=x$ if and only if $gxg^{-1}=x$, if and only if $gx = xg$. So $\varphi_g(x) = x$ if and only if $g$ commutes with $x$. Thus, $\varphi_g(x)=x$ for all $x$ if and only if $g$ commutes with all $x$, if and only if $g\in Z(G)$. Thus, $N=Z(G)$, so $\mathrm{Inn}(G)\cong G/Z(G)$, as claimed.
Whenever $G$ is finite and its automorphismus is cyclic we can already conclude that $G$ is cyclic.
Because as we already saw $G$ is abelian and finite, we can use the fundamental theorem of finitely generated abelian groups and say that wlog
$G=\mathbb{Z}/p^k\mathbb{Z} \times \mathbb{Z}/p^j \mathbb{Z}$. But the automorphismgroup isn't abelian and hence isn't cyclic.
For non finite groups the implication isn't true.
The following is from this link and only slightly reworded.
Let $G$ be the subgroup of the additive group of rational numbers comprising those rational numbers that, when written in reduced form, have denominators that are square-free numbers, i.e., there is no prime number $p$ for which $p^2$ divides the denominator.
Then:
The only non-identity automorphism of is the negation map, so the automorphism group is $\mathbb{Z}/2\mathbb{Z}$, and is hence cyclic.
The group $G$ is not a cyclic group. In fact, it is not even a finitely generated group because any finite subset of can only cover finitely many primes in their denominators. It is, however, a locally cyclic group: any finitely generated subgroup is cyclic.
Best Answer
If $G$ is abelian, then $\phi_g=\mathrm{id}_G$ for all $g\in G$.
Your error is in concluding that if $\phi_g = (\phi_x)^{\circ k}$ (that is, $\phi_g$ is $\phi_x$ composed with itself $k$ times), then it must be the case that $g=x^k$.
In general, if $\phi_g=\phi_h$, that tells you that for all $x\in G$, $gxg^{-1}=hxh^{-1}$, so $h^{-1}gx = xh^{-1}g$. That is, $g$ and $h$ lie in the same coset of $Z(G)$ in $G$; you can also understand that from the fact that $\mathrm{Inn}(G)\cong G/Z(G)$. So if $g$ and $h$ have the same image in $G/Z(G)$, then they are congruent modulo the center, but not necessarily equal.
Here, because $G$ is abelian, $G=Z(G)$. So the fact that an arbitrary $g$ is congruent to $x^k$ for some $k$ modulo the center is unsurprising: everything is congruent to everything else modulo $Z(G)$. You do not conclude $g=x^k$, you conclude that $g\in x^kZ(G) = x^kG = G$... which is of course true.
That said, it is in fact true that for finite $G$, if $\mathrm{Aut}(G)$ is cyclic then $G$ is cyclic, and of order of the form $2^mp^k$ for some odd prime $p$, $m=0$ or $1$, and $k\geq 0$. You can find a proof here. If $G$ is infinite the conclusion need not hold; see here and here.