State machine crashes (Cyclone II) - no idea why. How do I debug?

State machines usually crash because they entered into an illegal, undocumented state.

This can happen when an input signal that is sampled is either asynchronous, or poorly synchronized.

The signal goes to two separate parts of the state machine transition logic, and is interpreted as a H in one part, and a L in the other.

This can then cause a transition to an illegal state.

You don't show enough of your code to know how this might apply in your case. The module header, and how all input signals are generated, is necessary to know.

Quartus will on occasion re-encode the state machine in another form (usually one-hot) where each defined state is implemented as being encoded with just one state bit set. You need to look in your report files to see if this was done (or not). Doing this can be disabled by user control.

As you mention synchronous clock timing can also be a cause, but Quartus should be able to tell you which paths did not meet your 50MHz timing (if any).