Nios 2 won't run a new software configuration

Then, I guess the watchdog is responsible of the behaviour you observe.

When you power up the board, the design from flash is loaded and this enables the watchdog timer.

When you try loading the updated software with "Run As", Nios is momentarily stopped and the watchdog timeouts, thus triggering a reset and forcing a reload from flash.

This would also explain the even-good / odd-fault behaviour. On the first RunAs attempt the watchdog triggers a reset, but in this condition the software probably restarts with a disabled watchdog. Then, the next RunAS succeeds with the updated software, which conversely re-enables the watchdog timer.