I have had this issue for a few weeks now on my Acer iconia 501
When I set up the email, it worked fine with the recommended outgoing server details.
smtp2.vodafone.net.NZ
Port. 25
Security. None
User name. Full email address
Password. Imap/pop password
Require sign in yes

After searching the internet for a couple of hours and not finding anything that helped, I decided in a last ditch effort to play with the settings of the outgoing server.
Changed the security to SSL (Accept all certificates) and the Port to 465

I can now send emails again.