Ahh plex and the video start issues. When this last happened to me I paused the video then skipped ahead 10 seconds and the video loaded. I just tried this with my ATV4K and it worked. Have not tried it with the ATV4 yet.
Interesting, I never had issues like that before.
To further my post above I noticed Plex just pushed an update. I tried on my ATV4 and had no video issues.
Even more interesting! I shall get straight to updating it...