I guess it is not related to the clock crossing. Now, I found something else that is may be similar:
http://www.alteraforum.com/forum/showthread.php?t=47681 In the above thread, Steve observed that Nios fails to boot from flash at power-on. But subsequent FPGA reset allowed the Nios to boot correctly. In his finding, he found that the Nios processor started reading from the flash without complying to the flash minimum reset time after power-on. He made modification to the arbitration logic to delay the grant signal banck to Nios to make his design work.
Can you try to delay the grant signal back to the Nios processor? I can't tag Steve here for comment but will ask him to for more information on adding the delays.