Our search predict stopped working after integrating 3.5.1 update. I checked the DEMO http://demos.appthemes.com/?theme=classipress and the search predict is also broken there as well.
I checked difference with working and non-working versions and noticed it appears to be URL encoding in AJAX url string