連絡帳が検索できなくなる

再起動（電源オフにしてオン）してもダメですか？

それでダメならiTunesに繋いで新規デバイスとして復元してみるとか。

なお、検索そのものは、iPhoneのホーム画面からでも出来ます。ホーム画面で下向きにフリックすれば検索になります。この検索は連絡先の検索だけではなく、iPhone全体、web検索も含む全てが対象ですが、割合優先的に連絡先も検索されます。人名や会社名だけでなく、連絡先のメモ欄に書いてることも含めて検索できます。

失礼します、

もしiOSが最新になっていなければ、アップデートすることで問題が解消しないでしょうか。アップデートの前にバックアップを取り、できればiTunesでのアップデートが望ましいと思います。