I had this problem too because I was using a home ISP E-mail account. When I was connected to my home wifi, I was able to send messages. On 3G, I couldn't so I switched my smtp to my cell carrier. That worked but then I could not send when I was on my wifi. The work-around is to set up a gmail account and enable that account to send messages on behalf of your other account and use gmail server settings on your iPhone. Sounds complicated but it is pretty easy. Just google it and you will find instructions.