The trick is to create a group in your contacts. However, you can not do it on your iPhone. But there is a method:
Sync your iPhone contact with iCloud (so you will need to enable iCloud. You may disable it after searching is working again.).
Log on iCloud on you PC.
In iCloud contacts, create a group.
Sync your iPhone contact with iCloud. This may take some time.
After your contacts on your iPhone is synced with iCloud to have the newly created groups, you should be able to search again on iPhone.