There was a big change in the way Mavericks Mail works with Gmail. Previously, if you enabled the All Mail folder in gmail.com settings in the labels tab, you would end up with exactly double the number of messages you had. One in the regular folder you store the message, and another in the All Mail folder.
That changed with Mavericks. Now you want to make sure you have All Mail
turned on in that gmail.com IMAP/label settings screen and Mavericks Mail knows how to handle it without the duplicates like before. This might fix the issues you are having. If All Mail is off Mavericks Mail will not handle folders properly.
Image
So do this... quit Mail then go to the folder below by clicking the Desktop then Go menu then Go to Folder and paste this in and enter.
Code:
~/Library/Mail/V2/MailData/
Now delete the three envelope folders shown here.
Image
Now go to gmail.com and make sure you have that All Mail label set to show in IMAP and save the change.
Now launch Mail and wait for it to download all your messages and reindex everything. The message download is fairly quick, but the reindex happens in the background and can take several hours. Just leave it on all night and let it run.
What is happening is Gmail does not really use folders, but they use "labels" to simulate folders. So your Mail client needs to sift through the entire All Mail folder and find all message labeled "My Reciepts" for example and move them to a My Receipts folder in Mail. That takes time to complete.
If you already have All Mail at gmail.com turned on, ignore everything I just said.