Are you sure your outbound mail server is configured correctly (incorrect server, wrong port, wrong or missing password or having "Use SSL" turned on when it should be off are the most common)
Happens a lot on both my and my wife's rmini's on iOS 7. Does not matter on which network. Pleased to see iOS 8 has not been left out of this feature. Another reason not to upgrade.