Okay, it looks like nobody here has a solution. But I just got another email from Samsung Support with the following suggestion.
"I suggest you to sign out and sign back into the app.
To sign out, select Settings [on Amazon account], from the left menu, and then select Deregister your Device. Close the app, reopen, and then enter your credentials to sign back in."
That worked! I now have Amazon Prime Videos back and working.
I'm unable to sign back into the app, going back to the app I get the same screen that doesn't provide an option for signing back in, just the same "amazon" screen saying to contact if there are problems. I also tried clearing cache via unplug, hold down on button for 20 seconds after turning off (or on). So frustrating. Please help.