1. What version of Zen Cart ? Was it an upgrade? From what version?
2. What addons/contributions do you have installed?
3. What are all your settings in Admin->Configuration->Email Options?
4. Do all *other* emails go out fine ?
5. Does this affect *all* order-status-update emails, or just to certain email addresses?