Something changed with Edge 530 in cold weather

More likely that your battery has simply aged to the point that capacity is suffering greatly in cold weather.  All rechargeable batteries have a finite life and number of recharges in them.  Some ways to extend their life is not overcharging and in particular not fully discharging.  They last longest at 50 to 70% charged, and stored at that level.  I don't charge until right before the ride and I don't charge any more than needed to arrive at 60% of battery by the end of ride.  (That generally means I'm charging to about 85% before each ride.)

What I describe is true for any lithium ion batteries you use like phones and cordless drills, etc.

I'd be looking for a forum thread on changing the battery yourself or send back to Garmin to exchange for a refurbished unit; or time to upgrade to another model if that appeals to you.

I appreciate the attempt, but what you're talking about has nothing to do with this issue. My battery life hasn't changed noticeably in warm weather, and the battery was nearly fully charged when it turned itself off in the cold. They changed something about how the device is operating, and it is shutting itself off despite the fact that it is telling me that the battery is nearly full. 

I think the real problem here is that Garmin has updated the firmware and it automatically turns on battery save mode when the temperature is below freezing. That SEEMS like it would be a good idea, but the problem is that the unit uses less power in battery saver mode, which creates less heat, which means the device shuts itself off at a higher ambient temperature than it used to. I would like to be able to turn off the setting that forces the device to automatically go into battery saver mode below freezing because that would be MUCH better for my use case. I am 100% fine with having shorter battery life in the cold. I expect that. I am not fine with the device shutting itself off after 15 minutes when it says it has 95% battery remaining. 

What you say may very well be true, perhaps they did change the software.  That said, Garmin's specifications list the operating temperature range of the 530 to be from -4º to 140ºF.  You mention "sub 0* F temps", so you are likely below the advertised operating range.  Garmin 530 specs:  https://www8.garmin.com/manuals/webhelp/edge530/EN-US/GUID-F48A61D7-BA27-4E47-A406-98F52C88A976.html

They might have changed the software to protect the battery against attempting to use outside of the listed operating temperature range.  What I described previously is only part of the sensitivity lithium batteries have to operating and usage conditions.  They are also very sensitive to temperatures for usage and charging.  (Note that Garmin lists the minimum temperature for charging as 32*F.)  The response of these batteries is not linear, the damage to them accelerates rapidly as you approach the low temperature extremes.

So although you previously got away with extreme low temperature use perhaps Garmin did change the software to further protect the unit. 

Based on the sensitivity to charging below 32* (which is the common spec for all lithium batteries), if you are connecting an external battery pack during a very cold ride, it would be better to do so at the beginning of the ride so that you really aren't charging the battery, you're just providing an additional external power source.  That said, it still won't help your issue if the unit itself is shutting down due to the measured ambient temperature.

The only real solution would be to keep the unit in pocket to keep it warmer, but would only allow you to record the ride and not actually use it for navigation or any performance feedback during the ride.  I can't think of a way to keep the unit warm whilst mounted on the bike.

Kudos to you for riding during such low temps!

For your information, it was sub-zero, but within spec when this happened. I know how batteries work. Your mansplaining isn't helping. I'm looking for helpful information, not someone lecturing me with erroneous information to the actual issue here. 

I'm surprised your 530 worked below 20F, mine has never been OK with cold temps.  Since new out of the box when 530 was a new release, it would not work in temps colder than around 20F.  Behaves like you describe, it shuts itself down.  Mine also got the cold weather prompt about backlight a year or so ago, but no change in the poor performance in cold weather.  I always break out the old 510 when temps will be below 20F, that one will work for me when it is well below 0F.

I have never noticed this and ride below freezing all the time?  

You battery has aged - older batteries don't perform as well as new ones in the cold. It doesn't matter if you like it or not.