appleIDを変更したら電話帳がすべて削除されました。復元する方法はありますか？

旧IDでiCloudにサインイン

IDはメールアドレスなので、頑張って突き止めましょう。

Apple ID のメールアドレスや電話番号を忘れた場合 - Apple サポート (日本)

IDが分かればPWはリセット可能です。

Apple ID のパスワードを忘れた場合 - Apple サポート (日本)

＞旧IDとPWが不明なことから

＞別IDを新規作成しサインインしたところ

ここにお書きのように「新規作成」なので、

「旧ID」とは別の「新規ID」の方ですので、旧IDの方の電話帳は見ること出来ません。

＞端末内の電話帳がすべて削除されてしまいました。

「削除された」ではなく、新規IDは「 別人 」なので見ること出来ないだけのことと思います。

ですので、

＞旧IDでiCloudにサインイン

と、D300 さんがご案内下さっています。

頑張って、旧IDの「メールアドレス」を思い出してください。