Whenever I moved a message from my Inbox to a folder the message wasn't removed from my Inbox. On the forum and on some sites (e.g. DigitalTrends) the fix they mention, is to check the "Show in IMAP" setting in GMail.
For me that checkbox has always been checked, however the "Show in Label" was set to "hide". When I selected "show", it seems to have fixed the issue for me now too.
The only remaining issue I've with Mail app is the slowness of Sync (retrieving emails).
I switched last week to use Airmail, as Mail had those issues (until I applied the above fix).
Airmail seems much faster in picking up new mails, even when in the Mail app I click the button to get emails it takes a long time before it finds the new mail.
I'm happy with the above change in the GMail settings, it at leasts fixes the Inbox issue of Mail. If there was a fix for the retrieving mails issue as well, it would be awesome... but so far no luck yet.
Update: MacRumors mentions Apple is working on a fix for OS X Mavericks Mail App Issues.