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

Sign-in canceled due to internal error - CX500 and CX600

Issue
The Lync phones (CX500 and CX600) no longer sign in to Lync 2013. Error message states "Please verify that the domain entered is correct"

After factory resetting the phone I still got the same error briefly followed by "Sign-in canceled due to internal error.Please try again"

I tested to see if the credentials were working with:

Test-CsPhoneBootstrap -PhoneOrExt "2705" -PIN "12121"

I checked the DNS setup
Lync Phones usually require as a minimum Option 42 and Option 120 (then enable DHCP Options on the Front End with .

set-CsRegistrarConfiguration -EnableDHCPServer $true

I tested the DHCP options with the DHCPUtil.exe -emulateclient
I also ran wireshark to see the client getting the DHCP options, connecting to Lync, negotiating certificates and then just stop as if the credentials were incorrect

Cause
Unknown...
Even though the traces showed that the phone was getting all the required DHCP options and the phone was chatting to the Lync Front End, I still had no success signing in.

Fix
I am not hugely excited about the Phone Logs so before I resorted to digging into them I simply ran through the Lync Deployment Wizard (Step 2)...

That did the trick "sigh"

Other potential causes
http://support.microsoft.com/kb/2464556