I know what was the problem on my board. I am driving nCE signal from MAXII chip, so when this chip was not programmed correctly CYCLONE did not get the code from the bitstream. Quartus Programmer did not record the error of any kind, but the Cyclone did not get the code, so the Nios II debugger was not able to find the CPU inside for the same reason.
I have modified MAXII design to temporarly ground the signal going to the nCE of CYCLONE II and everything works fine, except I need to program this chain twice:
CYCLONE II is first on the list, so I need to make one pass to program MAX CPLD, then on the second pass to program finally CYCLONE. I have to fix it on the target board - lucky it is only a prototype.