If your email is a POP account, the provider's SMTP server (used to send email) may only accept connections from within their own network (in order to prevent someone from using their SMTP server to send SPAM). If your Wi-Fi is on that network and your 3g/4g is not, that could be the reason for your problem. Many email providers provide a way for users to login to the SMTP server so that email can be sent from outside of their network. Perhaps your email provider provides instructions for setting up such access on their web site.
I changed the "Period to sync Email" setting to "all" and got it working. Battery consumption seems to have increased as well. I have no clue why that allowed it to start working because everything I've read says the setting has to do with how long emails that have been received stay on the phone.