Hello.
Try logging into your gmail acct via webmail. Go into acct settings. gmail settings>labels. check to see whether you have the "all mail" folder to "show in imap".
What he said! Gotta be the case.
Not quite sure if that really all applied over 6 years ago.So, this had been driving me crazy for the whole day. I added, deleted, added deleted all freakin day! then it dawned on me. 2 STEP VERIFICATION from Google messes the whole thing up! Follow all other instructions about IMAP on line and disable 2 step verification in your Google + Account. Victory!