SmartThings engineers have said that there is nothing individual customers can do one way or the other to solve this problem. They are working on it on the platform level.
Multiple people have reported in other threads that they have not done anything at all with their system but that Alexa routines did indeed start working again in the last 12 hours or so.
I think this is a situation where the main thing that is needed is patience. If you want to reset or rebuild your system, you certainly can, but it should not be necessary for this particular issue.
