The following is inspired by the chapter Partition Polynomials in Riordan's Combinatorial Identities where $g(x)$ is analytic and $g(0)=0$. Find the Taylor series of $f(x)$ at zero by evaluating the derivatives of $f(f(x))=g(x)$ at $0$ in succession.
Set $f(0)=0$, giving $f(f(0))=g(0)=0$.
The first derivative gives $f'(x) f'(f(x))=g'(x)$, therefore $f'(0)=\sqrt{g'(0)}$ and $f'(0)=-\sqrt{g'(0)}$. Set $f'(0)=\sqrt{g'(0)}$ for this example.
The second derivative $f'(x)^2 f''(f(x))+f'(f(x)) f''(x)=g''(x)$ produces $f''(0)=\frac{g''(0)}{g'(0)+\sqrt{g'(0)}}$.
The first few term of the Taylor series are
$f(x)=\sqrt{g'(0)}x+\frac{ g''(0)}{2 \left(g'(0)+\sqrt{g'(0)}\right)}x^2$ $+\frac{ \left(-3 g''(0)^2+g^{(3)}(0) g'(0)^{3/2}+2 g^{(3)}(0) g'(0)+g^{(3)}(0) \sqrt{g'(0)}\right)}{6 \left(\sqrt{g'(0)}+1\right)^2 g'(0) \left(g'(0)+1\right)}x^3+O(4)$.
This solution is based on $g(x)$ having a fixed point. Technically the question stated is whether there is always a solution and is focused on counter examples instead of a broad general answer as I have provided. But it does raise the question of whether there is a connection between $g(x)$ not having a fixed point and the counter examples that the other authors have provided.