Just in case someone else ends up here: The M25P32 flash is not at fault. I have tansplanted it onto a DVK board (packages were close enough) and it works fine there. Also got a previous setup using an Explorer board(modified for SPI boot) and deadbugged flash chip working. Looks like the level shifter is causing trouble.
As far as i know, the FX3 needs a pull down resistor on SPI MISO for correct boot. Try this.
I gave it a try (added a 10k pull down to MISO), without success. This would also go against the recommendation in AN76405 (FX3 Boot Options) section 7.3:
Please note that external pull-ups should not be connected on the MOSI and MISO signals, as shown in Figure 6.
The FX3 DVK also doesn't contain any pull down on MOSI.
You have tested all the possible ways to figure out the issue.
It looks like there is an issue with the Level Shifter.
Even though you connected FX3 SPI Lines to far end of Level Shifter, which is connected to SPI Flash, there is a chance that there would be some resistance over MISO and MOSI lines due to the level shifter. This may be the reason the failure.
Have you tested by removing the level shifter from the board?
Yes, as said in AN76405, there should not be any Pull/pull down resistors on MISO and MOSI lines.