Thank you for posting your query on Microsoft Q&A.
Could you please confirm if the step you mentioned is working for the user? "At this point if you don't have access to the current MFA authenticator device you will need to use 'login another way' to use SMS MFA for this login."
Normally when a user changes their device they will need to enrol in MFA again, and if they cannot navigate to the "Security info" portal to do this, then an admin will need to take the action "Require user to re-register multifactor authentication".
This needs to be done for each individual tenant that the user is a guest in, as their MFA registration is unique to each tenant. The user may need to contact an admin in the guest tenant.
If the user still has access to the old phone but is having trouble reaching the Security info portal for a specific tenant they can hardcode the URL with the specific tenant id as follows - https://mysignins.microsoft.com/security-info?tenant=xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxx
Do let me know if this helps or if you have any further queries, I would be happy to help!