Recently my 2007 Mazda6 (2.3L I4) has been taking longer and longer to start in temperatures colder than about 5 F (-15 C). The car usually sits overnight for about 12 hours after I get home from work; it typically starts better when I’m leaving work in the afternoon. Today I had the key turned for about 4 seconds, then gave it a short rest and after another 2 seconds of starting it fired up. Normally it kicks up almost instantly.

The starter turns over quickly but the engine doesn’t catch, so I don’t think it’s a battery or starter issue. When it finally does catch, the engine lugs at very low RPM for several seconds and sometimes dies on me at this point. It starts up more easily after this though. Often I’ll give it a little gas right as it starts, then it lugs for a shorter period of time before spiking up to about 2.5k.

I have also had it start with no trouble but then lug at very low RPM until I rev it a bit. After this, it drives just fine and I have no reduced power while driving normally.

Other info:

• Vehicle has about 106k miles
• I replaced original plugs with NGK Iridiums about 10k miles ago when I bought the car
• Coil packs and wires are original
• Just replaced battery about a month ago with a Duralast Gold (590 CCAs)
• I know nothing about the state of the fuel system, but haven’t had any issues so far
• Turning the key to "on" and waiting for the fuel pump to shut off before starting doesn't seem to make any difference

Seems like a fuel pressure problem. Issues with coil packs doesn't seem likely. Any other thoughts? What tests should I do to figure out what to do next? (I can't test fuel pressure myself, would have to take it somewhere)

UPDATE

This morning it was right around freezing (slightly below freezing overnight); much warmer than it has been recently.

I still had a little trouble starting this morning, about 6 seconds of cranking then gave it a couple seconds rest and it started almost immediately on the second try.

I drove about 10 minutes to an appointment. The engine reached normal operating temp but I didn't go any faster than about 40 mph.

After about 45 minutes I came back out to my car and it wouldn't start at all - or rather, it would crank and quickly start to turn over but then immediately die. After 4 or 5 tries of this I started to worry I'd need a tow, but with a combination of holding the key on start and feathering the gas pedal, it finally choked and sputtered and then revved up to idle like nothing had happened. It ran fine all the way to work.

I'm becoming less convinced this is directly related to outside temperature. What should I test next?