Hi Blackhawk,
If the user's machine is joined to the domain and IIS is configured correctly on the server where the Web Service is running, and that server is part of the domain, you should not have any problems. You should make sure that the user's machine is joined to the domain. If not, the user can still connect to the Web Service, but they'll have to VPN in to the domain using their domain credentials. Once they are joined or VPN'ed in, the Web Service should see their domain credentials. If not, check your IIS settings using IIS Manager. It's possible you are not configured correctly.
Let us know if you are still seeing an issue. We use Web services a lot here with no problems. We also have a Web Service that doesn't require Windows Integrated Authentication - useful for accessing a Web Service from across the Internet when you don't have a Windows machine or aren't part of the domain....