Without a doubt, the biggest symptom of eroded away spark plugs (i.e. way over due to be changed) is stalling at idle, especially a cold motor in cold weather, rough idle, poorer performance and mileage. So being overdue for new plugs and having stalling, you did the first thing you should have, hopefully that will solve it.
Higher than recommended octane fuel can cause a cold motor to stall in very cold weather. Higher octane fuel is less volatile and thus vaporizes poorer than lower octane fuel, colder weather also makes it harder to vaporize and a cold motor is very sensitive to poor vaporized fuel. I.E. a bunch of drops and puddles of fuel are coming out of the injector into the cylinder, instead of a vapor of fuel going into the cylinder.
Fuel Injector cleaner can help, Chevron Techron most agree is the best and makes a difference.
But, really, you need to use the recommended octane for your motor, it designed to run off the fuel with those properties. Extra Octane really gets you nothing, so just use the recommended octane.*
*Higher Octane Fuel is also a little higher quality, it also uses a little less alcohol than the lower octanes, so that might account for the little better mileage that some folks have been able to measure when trying higher than recommended octane.
But if I was stalling a cold motor in cold weather, I would switch back to the recommended level of octane.