I've been having similar issues with my iPhone 5 and the latest iOS version. I read somewhere else about an issue with having Exchange and Imap in use with Mail being an issue. I had both, but had my Exchange connection to Gmail off. I was still having the issue.
The solution that worked was to delete my Exchange Gmail account. Now, emails are being sent immediately. If you have Exchange and Imap Gmail accounts on your iPhone, pick one and delete the other. Good luck.