Still having strange problems with SRAM and FLASH

Okay, let's get the "is it plugged in?" steuff out of the way...

Is the Avalon Tristate bus slave connected to the instruction master on the Nios II CPU as well as the data master? Does the data master have priority over the instruction master? With the pipelining, it may be trying to fetch something before it gets written out.

Also, in the Nios II Software Developer's Handbook, on page 7-5 there's a section "Writing Program Loaders or Self-Modifying Code." It might be useful, since what you describe also sounds like it's not seeing the instructions in question in the instruction cache, or they haven't flushed from the data cache to the external memory yet. The section on "Bit 31 cache memory bypass" may be useful, too.

Just some guesses. Good luck!