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