Last year, I had the same problem when it got cold. It was the fuel pump relay, so I bypassed it. We had severe cold again this week, and I am having the same problem. However, the fuel pump relay is already bypassed. I checked the fuses on the bypass and they are fine. I can hear the fuel pump turn on, as a matter of fact, it does not turn off until I take the key out and open the car door. The car gets stuck in the turn over position, so the starter appears to be working. I got a new battery already. Not sure what else to check. Maybe I need to get a new bypass.