Which version of NIOS are you using? From the screen dump it looks like you're using the older flash programmer which had infinite ways of mysteriously failing. It got much better in 5.1 so I would recommend upgrading to 5.1.
If you can't easily upgrade you might want to check your flash programmer design (the one in the "system" directory) to see if the timing of the flash interface is good and whether the clock frequency is fast enough. It's supposed to be faster than 50MHz, if I remember correctly.
Also, I don't know if the old programmer did some optimization where only the sectors that actually changed get programmed. Can you erase all your flash and see if it works after that?
Andrew