Are there any timeouts in your client application? Does only the first call fail or every consecutive ones also?
We have a similar situation with a client&webservice - when the first user in a day calls this webservice he sometimes gets an error which is basically a timeout expired. What we found out was that the IIS pool releases resources after some idle time and when the service gets its first call the resources need to be put into memory etc. The main consumer for this is Crystal Reports in our case.
After the first call is made and resources set the application works as expected.