It turned out that in our BSP for our custom board we had missed these lines in __pe_initialize_hardware() - they change the MUX for the pins to EXTAL1 and XTAL1:
/* PORTE_PCR24: ISF=0,MUX=0 */
PORTE_PCR24 &= (uint32_t)~0x01000700UL;
/* PORTE_PCR25: ISF=0,MUX=0 */
PORTE_PCR25 &= (uint32_t)~0x01000700UL;
Our oscillator is connected to EXTAL0 (PTA18) and XTAL0 (PTA19).
Even though our application project was subsequently changing the pin MUX to UART4 TX and RX we still had the problem described above.
After commenting out the above lines UART4 is working properly.
Thanks to Mike and David from Freescale for their help with this!