Let $G=(V,E)$ be a simple $2$-connected graph and $C$ is a cycle in $G$ satisfies:
For any vertex $v$ of $C$,there exists at least one vertex $u\in V(G)\backslash V(C)$ adjacent with $v$.
Is it true that there must exists a cycle in $G$ which is longer than $C$?
Here is a quick reduction. Hopefully someone else can finish it off. Since $G$ is 2-connected, it has an ear-decomposition starting with the cycle $C$. Next, when building the ear-decomposition, for as long as possible always choose ears $P$ such that both ends of $P$ are in $C$ and $P$ has two edges. Now consider the last ear $P'$. If $P'$ is just an edge $e$, then $G \setminus e$ is 2-connected and we win by induction. Thus, $P'$ has at least two edges. If $P'$ has at least 3 edges, then let $G'$ be the graph obtained from $G$ by replacing $P'$ by a path of length 2. Note that $G'$ is 2-connected, and every vertex in $C$ still has a neighbour outside of $C$ in $G'$. Thus, by induction, $G'$ and hence $G$ has a cycle longer than $C$. Thus, $P'$ has exactly two edges. If at least one end of $P'$ is not in $C$, then by replacing $P'$ with a single edge, we win by induction. Thus, both ends of $P'$ are in $C$. Therefore, every ear is a $C$-path with two edges. We can thus colour the edges of $C$ red and replace each ear with a blue edge. We now have a graph $G''$ with $V(G'')=V(C)$, and where every vertex is incident to a blue edge. I think it should be easy to show that such a graph has a cycle longer than $C$ (red edges have length 1, and blue edges have length 2).
Here is a proof for the simplest case, as you define it in your comment to Tony's answer. In this simplest case you essentially have a 3-regular graph that has a Hamiltonian cycle and you ask whether another Hamiltonian cycle exists. This is called Smith's theorem, see
http://mathworld.wolfram.com/SmithsNetworkTheorem.html
or
http://en.wikipedia.org/wiki/Handshaking_lemma#Exchange_graphs
I also think that every other case reduces to this one, through some not very interesting case analysis.
