Walmart is a corporation and has a corporate charter.
Corporate Charters are issued by the government, and as such those who hold them must abide by certain rules.
The government must act in the interest of the maximization of individual liberty.
If Walmart was a sole proprietorship, it should be allowed to hire and fire on a whim.
Walmart chose to become a corporate entity.
In cases where the rights of a Corporate Person are running afoul of the rights of a natural person, then the natural person should win- all things being equal.
So, yes. Wrongful termination. You can't fire someone for following the legal advice of a doctor.
If walmart didn't want to be subject to employment rules, they shouldn't have established themselves as a government-sponsored person.