You need to setup monitoring of the web service server. Specifically, you need to determine if the server is experiencing some type of contention. Monitor the following:
Processor -->%Processor Time
System--> Processor Queue Length
Physical Disk--> Current Disk Queue Length
Memory-->Available Megabytes
System-->Context Switch Rate.
As you increase the number of users. These values should change. If they do change, LoadRunner is not the issue. If they don't, add the Network Delay Monitor and rerun. This should reveal any network contention.
Record locking on the server side might also be the cause. If you are using the same data in each request, the server is probably locking that item at the database level. Until the lock is release, other requests will become queued.
Consider these and then update.