Hi,
I had the same problem when I tried to upload my image to the board.
It worked with the nios2download program, but it did not work sometimes with my own bootloader.
My bootloader loads the image from a serial flash into DDR by using a small program in a Mk4 block of the FPGA.
The problem turned out to be byte alignment.
Sometimes the zImage was even length then it worked, but when it was odd length it didn't.
To solve the problem I added 1 byte to the binary to make it even length, then it always worked.
Mybe your problem is similar to mine.
Note: I converted the elf format to binary to store it in my serial flash.