Didn’t see this mentioned when I glanced over the forum, but I recently started experiencing this issue a little over a week ago. Ended up being caused by my firewall blocking some AWS infrastructure hosted in the EU that Plex uses to determine remote connectivity. Recently implemented a Geo-IP ban so this makes sense. Looking up the IPs on IP Reputation tools like AbuseIPDB show that people have been reporting these IPs as malicious, so that could also be causing issues for anyone blocking IPs based on reputation.
This is actually covered in Plex’s Remote Access Troubleshooting page. They provide a link that dynamically updates the IPs currently being used. You can add this list to a whitelist.
