SignalTap II questions

You have fewer chances of getting timing problems when you reduce the clock frequency, but you could still have some (and even at low frequencies, you can have hold problems).

Are your input signals synchronized with the clock? If not, then you need to add synchronization stages on the FPGA inputs, to avoid metastability issues that could put your state machine in an unknown state.

Check also that the signal that resets your state machine is synchronously released with the state machine's clock.