Slightly different:
My iPhone was trying to send a movie via email. It had a little spinner to the left of it when viewed in the iPhone's Mail Outbox, indicating that it was trying to go out. I couldn't delete that message until I did this:
1. Quit the Mail app (double-tap on Home button, swipe up on Mail)
2. Put iPhone into Airplane mode
3. Start Mail, go to Outbox (and notice that the spinner isn't there now)
4. Swipe from right to left on the problematic email. Delete button showed up and I tapped it.
I hope this helps someone.
Of course you have to take your iPhone out of Airplane mode when you've finished with this. Remember to do that.