Some NIOS Interrputs don't seem to work

We are using 5 interrputs in a NIOS design (no RTOS) and when we use interrputs 0,1,2,3, and 4 we can't get them all to work. Specifically interrput 3 always gives us a hard time. When we read the NIOS interrput enable register, interrput 3 is not enabled even though is is set up in SOPC builder. However, when we use inttrrupts 0,2,4,6 and 8 the interrupts work. Has anyone seen an issue like this before? The Altera FAE has said that it is an FPGA timing issue but I still don't know how to fix it.