Sounds possible that not all of your mail was accessible via IMAP. Mine seems to work with all my labels.
http://help.cueup.com/customer/portal/articles/25915-getting...
http://help.cueup.com/customer/portal/articles/25915-getting...
I interacted with Greplin support, they were aware searches weren't finding things that had been auto filed by Gmail rules into labels. I have been annoyed this "for pay" service didn't handle this.
(Note that I do not expose the "All Mail" virtual folder through IMAP because that ends up doubling mail.)