After researching the above edit, we found that the problem was (apparently) related to SpamHaus.org blocking the relaying of emails through the cell providers into Zimbra. I turned off SpamHaus, and everything is working fine now...
Hope that helps if anyone else has this issue...