I managed to fix this very issue today.
Go to your devices on the Alexa app. Ensure the device that is being used for location routines has the correct location in its settings. Mine had reverted to an old address for some reason. Every other device I have had maintained the correct address.
I have no idea when or why this happened.
Hopefully this helps someone.