A simplified answer is: when you see a name in a purely functional language you know what the associated value is by a simple lookup of its definition. If you have mutable variables, you can only tell by which of the several assignments to it was executed last, so you have to also analyse control flow, which in turn might be conditional, leaving you with multiple possibilities. To get an exponential explosion you only need to consider that the RHS of the assignments are themselves dependent on variables, so you have to recursively analyse them too.
The bottom line in the above analysis is that it is untenable without comments explaining the intent, invariants, and semantics: these may be hard to interpret, and it may be hard to verify the semantics are adhered to in the actual code.
This answer is basically an expansion of @Javier's point 1.
I think it is also an explanation of the popularity of the fraudulent OO regime: with OO the mutable state is encapsulated which makes analysis a lot easier by localising the mutations to some extent, and permitting much more robust expression of and verification of semantics.
Having noted that, functional programming is not the answer. The right answer is a system which supports both inductive (functional) and coinductive (procedural) programming, so the right tools can handle both stateless and stateful programming. It's just that the constructive (functional) theory is well established whereas the theory of state management is still in its infancy.