The problem seems to have been the initialization to put it into EZPort mode. Works 100% of the time now. It couldn't find anything in the documentation but I realized that I had the "jist" of what I was doing in the original code but it wasn't exactly the same. The key bit seems to be that the chip select needed to be high (inactive) when power was applied and then set to low (active) before the reset line is brought low (active). Here's my original code (which is more succinct than the Kinetis code) in case someone runs into a similar problem in the future:
uint16 nPQSPAR = MCF_GPIO_PQSPAR;
uint8 nDDRQS = MCF_GPIO_DDRQS;
MCF_GPIO_DDRQS = MCF_GPIO_DDRQS_DDRQS3; // Set the port to output
MCF_GPIO_PQSPAR = MCF_GPIO_PQSPAR_QSPI_CS0_GPIO; // Sets EzPort Chip Select to GPIO
MCF_GPIO_PORTQS = MCF_GPIO_PORTQS_PORTQS3; // Set EzPort Chip Select to inactive (high)
// Power it down to avoid problems with the watchdog timer
GPIO_CORE_POWER_DISABLE();
Timer_Wait( 100 );
GPIO_CORE_RESET_ENABLE();
GPIO_CORE_POWER_ENABLE();
Timer_Wait( 1 );
MCF_GPIO_PORTQS = 0; // Set EzPort Chip Select to Active (low)
Timer_Wait( 1 );
GPIO_CORE_RESET_DISABLE();
Timer_Wait( 1 );
MCF_GPIO_DDRQS = nDDRQS;
MCF_GPIO_PQSPAR = nPQSPAR;