Try to get the water barrels up off the floor, its something about air conducting cold worse than solid - a pallet does the trick. If you see freezing, I might consider a roll of fiberglass insulation from Home Depot. Just like a blanketed water heater can keep the heat in, a blanketed water barrel might keep some of the cold out.

The pallet works out here in the PNW, I store water in an unheated attached room in 15 30 and 55 gallon drums. YMMV for Duluth and wherever you all may live.