iCloudに登録済のメアド（解約した携帯のメアド）を変更したい

iCloudの登録メールアドレス

と

AppleID

は同じもののはずですが…。

Apple IDのID名（アカウント名・主要連絡先）がそのままiCloudのアカウントですが…。なので、Apple IDのID名を変更したらiCloudの方も変更されているはずですが…。

「Apple ID を変更する - Apple サポート」

いまいち状況がよく分かりません…。

もしかして、サービスをサインアウトする前にApple IDのID名を変更してしまったという話？

『iCloudの登録メールアドレス』とのことですが、正確には、iCloudのサービスにサインインする時に使う、『Apple IDの主要メールアドレス』ということだと考えます。　なので、Apple IDの主要メールアドレスを変更するには、iCloud.comのサイトではなく、My Apple IDのサイトで変更します。　その方法はNO9さんが載せてくださったリンク先を参照してください。　（変更前にiPhoneを探すなどのApple IDを使うサービスから、サインアウトします。この手順を省くと面倒なトラブルに遭遇することになります）

Apple ID関連のメールアドレスについてはこちらも参考にどうぞ。

Apple ID のメールアドレスについて - Apple サポート

iCloudに前のIDのままサインインしている状態なのでしょうか？

もしそうなら、iCloudからサインアウトして、変更したAppleIDでサインインし直せば良いだけかと。