The issue could be either related to network related or the service itself is taking longer time to respond.
The first step would be to identify where the bottle necks is ? For example, use WireShark to see if the connection establishment is taking a long time.
As it is WCF service, you can turn on WCF trace logs on the server. Refer - http://msdn.microsoft.com/en-us/library/ms751526.aspx
WCF traces will give you details on what is happening on service side and is there any issue happening there.
