I figured out the problem...it does seem like there's a minor bug in Gesture Search, but easy to get around
I'm on Gesture Search 2.0.1, running on Jellybean 4.1.2
When I go Contacts/People, under settings, there is a setting for contacts to display:
I had the account for "Google" checked - Gesture Search was not able to find my google contacts despite this.
Instead, I had to go to "Customize", then go to my google accounts and manually check each label. With this, Gesture Search was able to see my contacts and finally work properly