This happens everytime the temperature reaches below freezing. I replaced the battery and it did not fix this issue, starts fine in warmer weather. Was thinking of buying another battery with more cold crank amps.
Any suggestions??

It is -3 Celcius this day

*WARNING: this sounds ugly *

 

I've had mine in -10 to -15C and never anything like that. Something is very wrong there.
A low battery will cause it to crank slower but not like that.

 

Wow that took 10 brutal seconds to fire up. Try testing the battery with a voltmeter before you replace it.

 

More info is needed: Year, mileage, etc

The battery is not the issue. The engine is turning over at a good speed. Its mis-firing during start up. If you have basic hand tools, I would pull a spark plug and check for gas and/or oil on the tip.

If you have access to an OBD-2 scanner, look at the long term & short term fuel trims. They should be between -10 to +10. It is difficult to start a cold engine with a lean fuel mixture.

-OR- Take it to a trusted shop and let them start it when cold.
Also, I noticed the KPH speedo, if you are in the GTA area, I could scan your car for a coffee

 

2008 Infiniti G37s 148,000km

A friend apparently saw black smoke out of the exhausts on startup on another cold day. I have never seen this myself, as im always in the front seat.
Could this be flooding this engine with fuel/Burning too rich? If thats the case, odd that it only happens in cold temperatures when the viscosity of the fuel/oil is thicker.

Im from Hamilton, I wouldn't mind throwing a scan on her.

 

Mine did this the other day and scared the ish out of me, cranked 10 seconds JUST like that until it started very rough.. I am interested to hear the findings as it hasn't happened to me since. It was, however about 10F here.

 

Black smoke on start up means the mixture is rich.

If a fuel injector is leaking when the car is tuned off, fuel will pool in by the intake valves or combustion chamber (depending on valve position). When you start the car in cold temps, a lot of liquid fuel enters the cold cylinder and ignition is difficult. Warm/hot engine will start fine, as the there will be more fuel vapour from the engine heat.

If you have access to tools, measure the fuel rail pressure at idle (~ 51 psi), then turn it off, and monitor the fuel pressure dropping. The FSM will have the spec on how slowly the fuel pressure should drop.