App Storeの請求先住所を変更したい

クレカのセキュリティコードは入力していますか？

肝心のクレカの登録住所は変更した後にやってますか？

クレカのサイトで変更してても、すぐには変更が反映してない可能性もあります。

クレカの情報を変更すると、それはAppleからクレカの発行会社にネット経由で確認に行きます。確認が取れて初めて変更できます。登録住所が違っててはクレカ会社から承認がおりませんので、Apple Accountの登録住所も変更できません。

そうなると、一旦削除して再登録するとか

削除直後だとサーバ上にキャッシュとか残っているかもしれないので、半日以上置いてから再登録が良いかと思います。