NIOS II Locking Up

I'd concentrate on the timing issue idea.

What's your system clock frequency? Can you momentarily reduce it and find out if you still have the same problems. Clearly you have to change it in the Quartus fpga project and rebuild all; this may be quite annoying but it should be straighforward and useful to understand the problem.

Another option is performing a basic TimeQuest analysis and look for negative slacks. With basic I mean using only the minimal clock constraints (see TQ tutorial) without bothering I/Os signals.