I'm interested to know - before the 10.9 upgrade, did you have "All Mail" visible in IMAP in your Gmail label settings?
Also, about how many messages did you have in the inbox that worked?
Also, about how many messages did you have in the inbox that worked?