Go to Settings > Mail, Contacts, Calandars, tap on your Gmail Account, and then toggle off contacts. Select "Remove from iPhone" when it asks. Then reboot and toggle it back on. Test to see if you can search for contacts after the reboot.Europa I am using Google sync. It serves all my phones including Android and windows.