Functional languages are a bit more difficult to think about, but that may be a combination of my inexperience and the implementations I've seen. OTOH, some problems do not deal with with lack of state. I'd really like to use Erlang, e.g., but I need mutable state. You can do it in Erlang, but you've got to fight the system to do it.
Note: I don't need externally visible mutable state. That's clearly dangerous in a concurrent system. I need internally mutable state. In Erlang that means either storing things in a hash table, a database, or a block of uninterpreted bytes. All ways that are clumsy to handle (and, I presume, slow). That Erlang allows this indicates that it is seen as something that is concurrently safe. But the difficulty in doing this shows that the designers of Erlang didn't see this as anything important for their use cases.
Now it's a good question whether or not you consider immutability a part of the definition of functional programming. Lisp allows mutable state, so does Scheme. So does Erlang. But they all discourage it and make it difficult to use. It's my contention that the definition should restrict itself to shared mutable state, but I'm not sure that this is the consensus.