problem from the cold?
clean ALL connections at the battery, and the ground, and on the solenoid.... (follow your large wires from both terminals on the battery and clean both ends... and what they connect to).
Battery needs to be fully charged to test properly...
check voltage at the battery with nothing on... should be a bit over 12 volts. (maybe up to 12.5). Then turn on headlights, ignition, heater on full, and see what it drops to... that is putting a bit of a load on it, it should stay at 11.5 or so....
then turn everything else off and start it, watching the voltage... it should go up to 13.5-15 volts when running....
BTW, Autozone should check your battery free, especially if you bought it there...