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.
State machine and linear workflow are sufficiently different problem spaces to be unrelated in terms of application development.
The process being modelled drives the approach, you use a state machine for a process that has a number of states in which the unit of work can exist and for which there is a potentially non-linear progression through the states. Where a clearly linear process exists, one for which there is no significant backtracking then a linear workflow (or sequential workflow) would be used.
State machine workflows are meant to be used when there is no predefined steps through workflow completion. Take a look into this definition (from State Machine Workflows in Windows Workflow Foundation)