Problem with search for Skype contact

The following error message is logged on the Front End server when trying to search for public Skype contacts:

Skype search request failed.

Exception information : Fault occurred while attempting to proxy WCF message.
Exception type: CommunicationException
Additional Data:
Source: Microsoft.Rtc.Server.WebInfrastructure
Stack Trace:
at Microsoft.Rtc.Internal.WebServicesAuthFramework.AsyncResult.End[TAsyncResult](IAsyncResult result)
at Microsoft.Rtc.Internal.WebServicesAuthFramework.HttpWcfProxyProcessor.EndProcessMessage(RequestContext context, IAsyncResult ar)
at Microsoft.LiveServer.DLExpansion.Service.EndSearchSkypeDirectory(IAsyncResult asyncResult)
Data: 0 key/value pairs
Inner Exception:The request was aborted: The request was canceled.
Exception type: WebException
Additional Data:
Source: System
Stack Trace:
at System.Net.HttpWebRequest.EndGetResponse(IAsyncResult asyncResult)
at Microsoft.Rtc.Internal.WebProxy.ProxyWcfRequest.GetResponseReadyCallback(IAsyncResult result)
at Microsoft.Rtc.Internal.WebProxy.AsyncCallbackWrapper.CallbackWrapper(IAsyncResult result)
Data: 0 key/value pairs
Inner Exception:

.
Cause: A configuration or network connectivity issue might be causing failure to access the Skype search service.
Resolution:
Check the Skype search proxy and network configuration.

No network issues on the server. 

Any help is deeply appriciated!