I did have quite a few problems with not all labels being backed up. 80% of labels did back up. At first, I thought it was because I was using the "nested labels" in Gmail labs. So I disabled "nested labels", re-ran the backup. That did not fix the issue.
Anyway, the missing labels did occur predominantly with certain senders, but I could not figure out a pattern among these senders.
Otherwise, it worked great.