Part of this is the governments fault, they drove so many postal employees nuts in the 70's & 80's the employees started killing each other... a lot. Google the term 'going postal'...
Those postal shootings resulted in lawsuits against the post office, but it also caught the attention of insurance companies. All businesses must insure the property they are on, just like you should insure your home, a large buisness, which Autozone is, has massive amounts of insurance, insurance for everything from storm damage to lawsuits from customers that slip in the parking lot and sue. Many of the insurance companies will require a large buisness to have a weapons policy before they will insure the buisness. Many city's won't let a buisness open without insurance and if the insurer requires a weapons policy.... you have to have it to open your buisness.
It sucks the guy lost his job. It sucks because lawyers and government employees screwed up this country so much that policies protecting the buisness are needed.