I had a 1.8 ADZ and had the same problem which turned out to be the coil. I couldn't figure it out because there was a spark on the King lead when the problem occurred so I also changed the fuel pump relay, the throttle mounting plate and coolant temp sensor.
It would never happen in the middle of the day cold start, just on early mornings which was weird. Used spark plug testers and noticed that the sparks were very very weak and got stronger after more cranking until it fired up. Apparently if the coil pack has a crack on it then dampness/moisture can settle in.
If you can, donor a coil when the fault happens. If you have done so already then hopefully the CTS will solve your problems as thats definately the next thing to measure. Have you scanned it for faults?