Thank you for the details! It seems like in this case a MFA reset should help sort out the issue, especially since you have mentioned changing your phone, which can commonly cause this error.
In order to request an MFA reset, please reach out through a DM to @support and provide the needed details according to our article on this topic.
Have a great one!
Gerald