Hi Bu,
Could be many things. Latency would be the first thing to look at (are you accessing this web service within a VPN, intranet or over the web?). Is there any encryption? Are you going through any firewalls? Maybe the webservice you are trying to consume is under heavy load? Maybe your application is under heavy load?
Could you please elaborate on "I tried to check what traffic goes over the network, but nothing, it just stays there.". Are you using a sniffer to monitor the traffic?
It may also be advisable to get the provider of the web service to look into it from their side.