If $Aut(G)$ is cyclic, $Inn(G)$ must be cyclic. However, I'm not exactly sure how $<Inn(G)>$ would be defined. Take, for example, $\phi_a(g)\in Aut(G)$, for some fixed $a\in G$. Then does a next element have to be $[\phi_a(g)]^2 = \phi_{a^2}(g)$?
Your help would be much appreciated. I don't yet have very good intuition about automorphisms.
Cyclic just means that there's some generator; it doesn't mean that there's a distinguished choice of generator. For example, if $p$ is prime, $\text{Aut}(\mathbb{Z}_p) \cong \mathbb{Z}_p^{\times}$ is cyclic. A generator is given by muliplication by a primitive root $\bmod p$, and it can be quite hard to find these.