When every streaming service in the world plays fine on Roku except Apple, it seems obvious the problem is on Apple’s side.
I tried all the solutions posted in this thread multiple times, including installing a new Roku streaming stick, and NONE of them work.
However I just discovered that when I get the dreaded “Video Not Available”, if I open the Apple TV app on my iPad and start playing a program, and then start Apple TV on Roku, it will play. Seems crazy, but it works.