Build gcc from the sources.
Or you could just do what the linux kernel does for tracebacks...
Just print every word from the stack that points into the code space.
(You could look at the instruction at the call site to supress some incorrect entries.)
You might also find that it is actually a simple bug in the gcc code for nios - possibly
a change that should have been done for gcc4, but wasn't.
The gcc4 and gcc3 nios support files are almost identical (well, were last time I looked).
Trouble is, fixing gcc either involves a lot of knowledge, or some blind faith!