State machines can reduce complexity of workflows when there are multiple loops and branching or logic when the workflow must "react" to answers supplied by users. This would be an event-driven workflow.
In what circumstances have you elected to use a state machine and what type of pain did reduce in terms of time and complexity?
State machines are really nice for event-driven code. You can't use loops and branches if your code is being invoked as a response to some event. You'll have to use a state machine instead, feed the events into it to change the state, and have the event handler react according to the machine's current state.