I just remembered a problem I had when I first started with NIOS II (it magically disappeared so I forgot about it).
The CPU might need to be held in reset for a bit longer then the actual reset signal. You can do this using the hardware
in the sample that they give you (it was a down counter that started from the reset being triggered and delayed the
reset to the CPU for quite a few clock cycles). I don't remember all the details, but if you look at the same design you'll
know what I'm talking about since there is some logic in there that doesn't look like it should be there at first glance.
G-luck.