Hi
If your contacts side have upgraded their Lync servers to Skype for Business then it may be an issue with their side depending on the upgrade path they have taken. If there have been no changes on your system then it is unlikely that it will be your side.
However, saying that, there are a few things to check your side
1) On your Lync server > Federation and Ext Access > SIP federated Domains - If you are explicitly allowing federated partners and not performing partner discovery then it may be that their access edge FQDN may have changed and you are looking for
a service that is no longer there. Remove the Edge FQDN from the allowed domain and save (this is not needed if the other side have configured their DNS right).
Wait for around 15 to 30 minutes for the Lync config to take effect.
2) If still no joy, have you tested whether you can contact the external contact from another computer and using a colleagues account?
3) See if you can telnet to your partner's access edge FQDN on port 443 from your edge server
thanks