Second NIOS often can't boot up

Did you poll the cpu_resettaken before de-asserting the cpu_resetrequest signal? The cpu_resettaken is some sort of an acknowledgement/handshake signal for the incoming cpu_resetrequest. cpu_resetrequest should not be a toggling or de-asserted until the cpu_resettaken goes high.

The cpu_resettaken is also affected by Nios internal pipeline stalls. Maybe due to accessing long latency slave from the instruction or data masters. You can try to tap the signals at the Nios B interfaces to see whether there is any on-going activity.