I have no idea what the law is in VA.
Most likely, the company probably has the legal right to tell its employees that they cannot bring a firearm onto company property.
The guy has obviously been bringing the firearm onto company property (their parking lot) despite the policy.
Therefore, he got fired.
Do I agree with it? No. But most likely that's the case.
Or, it could be like Indiana, where you can have a gun locked in your car in your employer's parking lot, but you can't take it out of your car. In Indiana, there is a law that prevents employers from banning guns in their parking lots except for certain types of businesses, like government offices, schools, etc... my employer leases a parking lot from a church for its employees to park in. That church has a day care and preschool, therefore, I could not bring a firearm into the parking lot even locked in a box and locked in my trunk and even if I had a permit to carry.
As someone else mentioned, boycotting Autozone will do nothing but hurt the employees that still work there. Voice your displeasure to their management.