It's no secret that Mavericks' Mail.app and Gmail (and Google Apps) are not getting along. Gmail is a non standard IMAP email system and Mail.app also made some changes in how it handles Gmail. Since upgrading to Mavericks, Mail.app has been quite 'wonky' for me.
I mentioned my frustration on Twitter and a lot of folks recommended that I try Airmail. It was only $1.99 in the Mac App Store, so I took the plunge. It's really fast and has better Gmail support out of the box. It supports iCloud, Hotmail, Gmail, Exchange, and others. This is one of the nice things about the Mac compared to iOS. It's possible to change the default email client on the Mac where it's not on iOS. Apple appears to be testing patches for the Gmail issues, but I think I am going to stick with Airmail for the time being.