1998 toyota corolla will not start in cold weather.

I have had my corolla for about a year now and am starting into the second winter with it. Last night was the first night that the temp was below 45 F and this morning my car will not start. It will not even turn over, nothing! I had this problem again and again last year. A couple of times it would start later in the day but most of the time it would remain dead the whole day. I ended up taking the battery to wal-mart to have the amps checked and was told it was not good, so they gave me a new battery. My car then worked fine for about two weeks, then it died again. ( I don't know if I should mention the temps reach about -30 at night here in the winter). One day it was working fine and the next day the power locks, lights, nothing works the engine does not even turn over!

Someone mentioned once that I may have a draw on my battery but after winter ended I had no problem with my car not starting. It has worked perfectly fine through the entire spring and summer starting flawlessly! So I really just don't know what to do! Any advice would be much appreciated! I have the same problem with my Toyota Avalon 1999. Some time it doesn't start in first few cranks in cold weather and once I pump the gas it just start. When the engine is warm, the car starts in first crank. I installed the new spark plugs, but it didn't worked out. I checked the battery and alternator through Autozone and they found both good. Can anybody let me know what is the problem.