With unsynchronized inputs, you can run into metastability problems. If your input signal changes to close to the clock edge and it doesn't follow the setup/hold requirements, then the flip/flop may oscillate between two states, which can have bad consequences on the rest of the design (including unwanted states).
The solution to the problem is to register all the input signals with several flip/flops in series. 2 or 3 stages are usually enough.
Check also that the clock you use in signaltap is the same than the one that's running your state machine (or at least synchronized with it). If not you could miss the synchronization between all the signals you are measuring.