When you turn the key on do you crank it as soon as the wait to start light goes out?? At that temp you will have to wait a little longer with the key on after the light goes out. Try turning the key on, wait for the light to go out, the wait another 30 sec and see how it does. I can almost bet it will fire up then.