書かれていないのでWindowsのコンピュータを持っていると仮定して書きますね。
iTunesもダウンロードされているていで。
まず、「バックアップからの復元」はされましたか?
iCloudと同期されているならすぐに戻せますが・・・
復元には2種類あります。
1つは、iPhoneなどをiTunesに繋いだときに表示される「復元」
これは、設定を全て初期化して買ったときの状態に戻すやつです。
もう1つが、「バックアップからの復元」です。
iTunseを起動したら左のメニューに「~のiPhone」と出ます。
その上で右クリックすると出てくるメニューにあるものです。
された記憶が無いなら下記の手順で試してください。
1.絶対にiPhoneを繋がずにiTunesを立ち上げます。
なぜ繋いではいけないかと言うと、iTunesは設定を変えていない限り、
繋いだだけで同期とバックアップを自動で行います。
この時、バックアップが上書きされて、
質問者様の連絡先の入ったバックアップデータが消える可能性があります。
2.上にあるメニューから「編集(E)」を選びます。
3.出てきたメニューの中から「設定(F)」を選んでください。
4.「一般環境設定」というものが出てきたので、「デバイス」を選んでください。
5.「iPod,iPhoneおよびiPadえお自動的に同期しない(P)」と言うものが真ん中辺りにあると思うので、チェックをつけてください。
ここでついでにバックアップも確認してください。
質問者様がバックアップを取った時間と日付が表示されていれば、データは残っています。
6.その後、OKを選択します。
これで自動的にバックアップが上書きされなくなりました。
7ここで、やっとiPhone 3Gを接続してください。
8.左のメニューに「デバイス」「~のiPhone」と出てきたと思いますので、「~のiPhone」の上で右クリックを押してください。
9.出てきたメニューの「バックアップからの復元」をえらんでクリックします。
10.完了したら、連絡先を確認してみてください。
これで、直らない場合ですが、考えられる理由として、
1.自動バックアップ設定により、何も無い情報が上書きされてしまった。
2.可能性は低いですが故障。
~と言うアプリをダウンロードしたら直った!!とかも聞きますね。
意外と報告例や解決策もあるみたいですが、Appleの認めていない方法かもしれませんので
「iOS5 アップデート 連絡先」などで検索してください。