It had state mutation as a massive liability - which is probably why FP has seen such a surge in recent years. Rust is the only language that mostly solves that without totally changing the paradigm.
It doesn't really change the paradigm compared to FP even, it just enforces a clear separation at all times between sequential state mutation on the one hand and references to shared (and generally immutable, except as provided for by explicit mutability mechanisms) state on the other. Which is essentially what FP languages end up doing, though they go about it somewhat differently.
Right. The problem is that functional purity always comes with overhead; data structures like Clojure's help a whole lot, but there's still a cost.
But one of the primary motivators for functional purity is to avoid unintended side-effects.
In pure FP, You never even have to bother your mind with unexpected side-effects because there are no side-effects.
Rust instead gives you the vocabulary to carefully articulate intended side-effects, preventing all other, unexpected side-effects at the same time. So you can colonize the wilderness, instead of avoiding it altogether, and for that you get to skip the overhead of treating everything as immutable. Not that this is an indisputable improvement for every use-case, but it's a novel tradeoff and one that is definitely preferable in many domains.