There are no Nios II CPUs with debug modules available

Is your clock input correct? You could redirect it to a fpga output pin and check it with a scope, to be sure the FPGA is picking it up correctly, or feed it to a PLL and check the pll's "locked" output with Signaltap.

What does Timequest say? Does your design meet all the timing requirements and are all the paths correctly constrained?

If you go into System Console and scan the JTAG chain, do you see the Nios CPU and the JTAG UART in the connections tree?