携帯を新しくして4g接続できなくなった

勝ちゃんさんも書かれていますが、Aプランなのが間違いないとして、iPhoneでお使いのSIMは黒い非VoLTE SIMではありませんか？
以前のiPhoneが6以前ならこれです。iPhone 6s～7,SE(第一世代)ならこの可能性があります。

mineoアプリの右下…(その他)から「ご契約内容」を確認してみてください。VoLTEの文字が無いときは、下記を見てSIMを無償交換してもらいましょう。

（6月10日 15時40分追記）mineo Aプラン 3G停波に伴う影響について （nano / micro SIMカードをご利用中のお客さまは必ずご確認ください）
https://king.mineo.jp/staff_blogs/1615