LPE wont sign in to Lync externally

The Problem

Lync Phone Edition (in my case Polycom CX500 and CX600) wont sign in to Lync from externally. Internally working fine.

The phone goes through the steps of finding the time server, then finding the Lync Server - OK. Then gets stuck on Signing in... Connecting to Lync Server
This also happened to the CX600 EVEN when pairing to my desktop over USB for sign in...

The Evidence

Checking the Lync Edge Server logs I found...nothing! Same as the Front End, also nothing!
Since everything else seemed to be working I started to wonder how the LPE's are different from the desktop client.
Going through the motions of validating the DNS using the RUCT.exe tool I found that when I tried to test the port availability on selected records on the SRV record for -sip._tls I got an error stating that the host was not found.

What I found was very interesting. The SRV record for  _sip._tls.sipdoamin.com resloved to sip.sipdomain.com BUT the Public Certificate Common Name was LyncEdge.sipdomain.com with the name sip.sipdomain.com as a Subject Alternate Name.

The Solution

I changed the the SRV record so that the target was the published public name LyncEdge.sipdomain.com. Effectively this meant that the SRV target was also the Common Name on the Public Certificate.

NOTE
The Common Name on the Public Lync Certificate should always be a resolvable target for the SRV records