It was a known bug for version 3.5, where in some cases the fulltext search class is used instead of the regular. Fulltext has a minimum character count for matches, whihc is usually 4 by default.
The solution was simple, I saved the fulltext search settings page without changin anything to update the option values. This bug might appear if the plugin deactivated then activated or if the database or the whole installation is moved.
On a side note, I think your site is the fastest wordpress site I have ever seen in my life – including the search engine ajax request response times.Best,
If you like my products, don't forget to rate them on codecanyon :)