Problems in updating my Apple ID

My email was hacked (third party) so I must change my Apple ID ASAP , I opened a mew iCloud.com address but when I try to change my ID a massage shows saying “ you can only add the @icloud.com address that is already on file in your account”

Currently my I cloud address is listed in my contact info , as an alternative email.