Google has never had anything approximating what you could call a normal IMAP implementation for Gmail. However, under Mail in OS X 10.8 Mountain Lion and previous versions, many of us learned to work around and otherwise live with it. No longer! OS X 10.9 Mavericks changes the way the Mail app works, and in doing so, is less forgiving of Gmail's idiosyncrasies than ever before. Joe Kissel on TidBITS:
Mail and Gmail were never a fantastic combination out of the box, because Gmail has a wacky, highly nonstandard way of using IMAP, and Mail always wanted to treat Gmail as though it were a conventional IMAP server. But, after much trial and error, I eventually found a combination of Mail settings and Gmail settings that, prior to Mavericks, resulted in a stable — and indeed largely pleasant — experience. As I documented in “Achieving Email Bliss with IMAP, Gmail, and Apple Mail,” 2 May 2009, you just do x, y, and z (well, 21 steps’ worth of x, y, and z), and it’ll all work smoothly.
Well, forget about that under Mavericks. In fact, following those old directions now will lead you far from bliss. And if you followed them before upgrading to Mavericks, you’ll need to take some steps to undo some of the problems.
Gmail in Mail over IMAP has always been a pain for me. I never hid All Mail, so that's not a problem now, but it uses a ton of disk space and up until recently kept generating simultaneous connection and bandwidth usage errors.
I have a paid Google Apps account, so on iOS I simply use Exchange for Gmail via Google Sync, which works much, much better, and faster. Sadly, Google doesn't seem to allow for Exchange connections on OS X.
So, unless and until Apple changes Mail for Gmail's sake, or Google figures out how to better serve IMAP, we'll stay caught, painfully, in the middle.
Check out Joe's article for some small amount of relief, and if you're struggling with Gmail in Mail.app, let me know how it's going for you.