State machine transitioning into illegal state

I am working with a simple state machine with 4 states. The state machine is properly detected by Altera's state machine optimizer, and the state diagram it produces is correct.

When I probe this state machine with Signaltap, I find that it's entering an illegal state (all 4 state signals are low). Signaltap image is attached, triggered when all states == 0. This is an intermittent problem that does not occur every time.

This state machine does have asynchronous inputs (transmit_req), but they are all synchronized with code similar to that below.

always @(posedge Clk, negedge Rst_)
	if (~Rst_)
		safe_transmit_req <= 2'b0;
	else begin
		safe_transmit_req	<= transmit_req;
		safe_transmit_req	<= safe_transmit_req;
	end

The transition that is failing is conditional on ~safe_transmit_req[1]. It leaves the state, but instead of going to the correct state (st_fabric_Idle), it enters some unknown state.

st_fabric_Ack: begin
	fabric_transmit_ack	= 1'b1; 
	if (~safe_fabric_transmit_req)	begin	
		sm_tx_fabric_next	= st_fabric_Idle;
	end

The resets aren't shown but, even if it was getting reset, it should transition to the idle state. Does anyone see any glaring errors that would cause it to enter an illegal state?