After trying everything from deleting app data and clearing cache, to re-installing the Fire Plex app. Finally, found this little tweak. After selecting your show/movie, don’t click on Resume right away. First navigate away to another button, say Play from beginning, and then come back to the Resume button and click.
This has worked for me, but there is still a bug nonetheless in the latest version of Plex app.
