新しいiOSの問題とは考えにくいです😟
現に私のiPhoneも8.4.1ですが着信履歴は残ってますので…
製品が変わっても同じ症状が出るのは何かしらのデータの問題が考えられるので、
まずは上記にも書きました不要なアプリがあれば消す。
それから設定>一般>リセット>すべての設定リセットを試す。
(恐らくサポートセンターでも同じ指示があったかとは思いますが)
一番大事なのは復元です。必ずiTunesもしくはiCloudへバックアップをし、iPhoneを復元します。
https://support.apple.com/ja-jp/HT203977
https://support.apple.com/ja-jp/HT201252
工場出荷時の状態になるのと同時に新しいiOSをインストールしてくれます。
初期画面からの立ち上げ方はhttps://support.apple.com/ja-jp/HT202033を参照してください!
※ここで重要なのがiPhoneを設定の画面で新しいiPhoneとして設定を選択することです!
他の設定は立ち上げた後でも変更できるので適当にパパッと飛ばして飛ばして…
空っぽの状態でiPhoneが立ち上がったら一度誰かに電話してもらい着信履歴が残るか確認します。
時間のかかる作業ですし、データのバックアップを取るとはいえ不安でしょうから心配であればサポートセンターでサポートを受けるのも良いと思います
長くなりましたが頑張って!