Plex Cert Expired - Plex Clients (Shield, Sony Android TV App, etc) Cannot Connect

You now have a brand new certificate, since your server is also brand new.
Let it sit running for a few hours.

In the meantime, see Important note about Chrome and Firefox Local Network Access
as well as https://support.plex.tv/articles/206225077-how-to-use-secure-server-connections/