Doesn't look like a cert error. Did you try restarting PMS, PlexConnect and the AppleTV. You can also try forcing transcoding in the settings to see if its an error with the file format.
Okey, if i start the Plex Connect without PMS i get this : 18:44:46 DNSServer: DNS request received!
18:44:46 DNSServer: Source: ('192.168.1.90', 62362)
18:44:46 DNSServer: Domain: init-p01st.push.apple.com
18:44:46 DNSServer: ***forward request
18:44:46 DNSServer: -> DNS response from higher level
18:44:46 DNSServer: DNS request received!
18:44:46 DNSServer: Source: ('192.168.1.90', 60235)
18:44:46 DNSServer: Domain: 30-courier.push.apple.com
18:44:46 DNSServer: ***forward request
18:44:46 DNSServer: -> DNS response from higher level
18:44:47 DNSServer: DNS request received!
18:44:47 DNSServer: Source: ('192.168.1.90', 64725)
18:44:47 DNSServer: Domain: init.itunes.apple.com
18:44:47 DNSServer: ***forward request
18:44:47 DNSServer: -> DNS response from higher level
18:44:48 DNSServer: DNS request received!
18:44:48 DNSServer: Source: ('192.168.1.90', 55392)
18:44:48 DNSServer: Domain: EVSecure-ocsp.verisign.com
18:44:48 DNSServer: ***forward request
18:44:48 DNSServer: -> DNS response from higher level
18:44:48 DNSServer: DNS request received!
18:44:48 DNSServer: Source: ('192.168.1.90', 61641)
18:44:48 DNSServer: Domain: EVIntl-ocsp.verisign.com
18:44:48 DNSServer: ***forward request
18:44:48 DNSServer: -> DNS response from higher level
18:44:48 DNSServer: DNS request received!
18:44:48 DNSServer: Source: ('192.168.1.90', 60491)
18:44:48 DNSServer: Domain: configuration.apple.com
18:44:48 DNSServer: ***forward request
18:44:48 DNSServer: -> DNS response from higher level
18:44:48 DNSServer: DNS request received!
18:44:48 DNSServer: Source: ('192.168.1.90', 57488)
18:44:48 DNSServer: Domain: xp.apple.com
18:44:48 DNSServer: ***forward request
18:44:48 DNSServer: -> DNS response from higher level
18:44:48 DNSServer: DNS request received!
18:44:48 DNSServer: Source: ('192.168.1.90', 53700)
18:44:48 DNSServer: Domain: itunes.apple.com
18:44:48 DNSServer: ***forward request
18:44:48 DNSServer: -> DNS response from higher level
18:44:51 DNSServer: DNS request received!
18:44:51 DNSServer: Source: ('192.168.1.90', 56725)
18:44:51 DNSServer: Domain: se.itunes.apple.com
18:44:51 DNSServer: ***forward request
18:44:51 DNSServer: -> DNS response from higher level
18:44:51 DNSServer: DNS request received!
18:44:51 DNSServer: Source: ('192.168.1.90', 61937)
18:44:51 DNSServer: Domain: a4.mzstatic.com
18:44:51 DNSServer: ***forward request
18:44:51 DNSServer: -> DNS response from higher level
18:44:51 DNSServer: DNS request received!
18:44:51 DNSServer: Source: ('192.168.1.90', 52346)
18:44:51 DNSServer: Domain: a2.mzstatic.com
18:44:51 DNSServer: ***forward request
18:44:51 DNSServer: -> DNS response from higher level
18:44:52 DNSServer: DNS request received!
18:44:52 DNSServer: Source: ('192.168.1.90', 52573)
18:44:52 DNSServer: Domain: a1.mzstatic.com
18:44:52 DNSServer: ***forward request
18:44:52 DNSServer: -> DNS response from higher level
18:44:52 DNSServer: DNS request received!
18:44:52 DNSServer: Source: ('192.168.1.90', 57783)
18:44:52 DNSServer: Domain: a5.mzstatic.com
18:44:52 DNSServer: ***forward request
18:44:52 DNSServer: -> DNS response from higher level
18:44:52 DNSServer: DNS request received!
18:44:52 DNSServer: Source: ('192.168.1.90', 64774)
18:44:52 DNSServer: Domain: a3.mzstatic.com
18:44:52 DNSServer: ***forward request
18:44:52 DNSServer: -> DNS response from higher level