I have this problem as well, since updating to Mavericks, and also doing the recent Mavericks update which was supposed to improve gmail interoperability.
For example, earlier today I was expecting an email and it did not appear in Apple Mail, after manually clicking Get All New Mail. I had the activity window open and watched it complete the progress bar for checking new messages. However the mail did not appear, even though I could see it sitting right in my Google inbox.
I decided to test again a couple hours later in case it was a peak traffic time. Right now, I can see four new messages in my gmail webmail app (using Google Apps) in my web browser. All of them arrived in gmail more than 30 minutes ago. In Apple Mail, I manually select Get All New Mail several times, and they still don't appear in Apple Mail.
Again, I watched the progress bars complete in the activity window. Still, they do not appear in Mail.
Jeremy, this is not related to the automatic "check for new messages" setting, as I am manually checking them repeatedly.
EDIT: All the missing messages did appear after a quit and relaunch of Mail