I am using the Debug config for both libraries and the example. My MQX environment variables are exactly as you indicated.
Here is the full error message (tried building the gpio example this time):
Fatal Error[Pe1696]: cannot open source file "mqx_cnfg.h" C:\Freescale\Freescale_MQX_4_0\lib\twrk40x256.iar\debug\bsp\mqx.h 84
searched: "C:\Freescale\Freescale_MQX_4_0\lib\twrk40x256.iar\debug\bsp\"
searched: "C:\Freescale\Freescale_MQX_4_0\mqx\examples\gpio\"
searched: "C:\Freescale\Freescale_MQX_4_0\mqx\examples\gpio\iar\gpio_twrk40x256/../../../../../lib/twrk40x256.iar/debug/psp\"
searched: "C:\Freescale\Freescale_MQX_4_0\mqx\examples\gpio\iar\gpio_twrk40x256/../../../../../lib/twrk40x256.iar/debug/bsp/Sources\"
searched: "C:\Freescale\Freescale_MQX_4_0\mqx\examples\gpio\iar\
gpio_twrk40x256/../../../../../lib/twrk40x256.iar/debug/bsp/Generated_Code\"
searched: "C:\Freescale\Freescale_MQX_4_0\mqx\examples\gpio\iar\gpio_twrk40x256/../../../../../lib/twrk40x256.iar/debug/bsp\"
searched: "C:\Freescale\Freescale_MQX_4_0\mqx\examples\gpio\iar\gpio_twrk40x256/../../../../../lib/twrk40x256.iar/debug\"
searched: "C:\Program Files\IAR Systems\Embedded Workbench 6.5\arm\inc\"
searched: "C:\Program Files\IAR Systems\Embedded Workbench 6.5\arm\inc\c\"