Lync to Skype federation requires provisioning from Microsoft side

https://pic.lync.com/provision/Logon/FAQ.htm

Some other notes that I can add:

Skype may not like SHA256 (SHA-2) signature on the endge certificate. Check if you can reissue your public certificate with SHA1 (less secure).

Note that egde must trust  "Baltimore CyberTrust Root" as this is what Skype uses.

It may take another 2 weeks after you get email from Microsofdt that provisioning is finished.

Do not forget to enable

Set-CsMediaConfiguration -EncryptionLevel SupportEncryption
Set-CsExternalAccessPolicy Global -EnablePublicCloudAccess $true -EnablePublicCloudAudioVideoAccess $true

as exaplained at http://technet.microsoft.com/en-us/library/jj205149.aspx