This is a consistently reproducible, and pretty annoying bug.
Player: Nvidia Shield Pro with Android Plex app.
When initially selecting a TV episode to play, subtitle search works.
However, once I have allowed the next episode to begin via auto-play, the subtitles search always fails with an error. If I exit the episode, and play that episode directly (instead of being “inside” the auto-play) the subtitle search will then work fine.