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