This line has me confused. Firing good and fast. Won't turn over??
Firing good and fast is typically the opposite of won't turn over
First off what is the CCA of the battery you bought. For that cold you should max out the CCA of the group size battery. I think something in the 700s.
A trick with getting a cold battery to start flowing juice is to turn on a couple of accessories prior to cranking. Like turn the key on. Turn on the radio and the highlights on bright. Let is sit like that for 30 seconds. Turn off the lights then crank.
I would also check the battery terminals. Make sure they are clean and tight.
-7 is cold but not that cold. I have started my truck a couple of times in those temps. I also have a 600 or so CCA battery.