Was still happening at 2 AM EST, but as of 8 AM, it seems to be fixed.
For those still having this problem, here's how I ended up working around it: Get on the Prime Video app on my phone, find what I wanted to watch, press the button with the 3 vertical dots on the lower right, hit the "Watch on" button, select Fire TV Stick. Worked like a charm.
I had the same issue last night. I ended up just buying one of the movies I've watched previously with Prime; the other program was a multi-episode program that would let me watch part of it, but if I left it, I couldn't get back to the episode I was watching and would get the "30-day Prime trial." But every other episode was available, so I had to scan through it to the end when "Next" would show the next episode and it came up without the 30-day Prime Trial offer. Too strange.
I did the same thing with The Sopranos. The episode I wanted wouldn't work with the "30-day trial" nonsense, and it would only give me other options like Bravo TV (with commercials, I'm sure) and buying or renting it. No way. But I found an earlier episode in my history with "Continue Watching" highlighted, so I selected it, then went on to "Next Episode" several times until it got to what I wanted.
Later, I discovered that using the phone app (which works fine) and telling it to send what I want to watch to the FireTV stick sidesteps all this nonsense. (See my earlier post above for details.)