I have an update. After talking to somebody using Shopify Support, I received a reply saying that my issue was fixed, and I just added the MX record without any error.
In summary, get in contact with Shopify Support, they will try to fix it, if they can’t, they will open an internal ticket and then fix it.
Merry Christmas guys!