I guess some more information is needed to diagnose this.
- How is your ArcGIS Server configured in terms of security? Are you using token based security? Does your server use windows authentication against the services via IIS? I'm thinking that windows authentication comes into the picture from the error messages.
- What is you client running on? Is it a Windows machine connecting to a Windows Server based ArcGIS Server?
- What does your code look like?
- From the client, if you open up a browser window, can you browse the service endpoint for the geoprocessor?
If you are using token based security (which is the most common authentication I see), you set up your user credentials with a username / password and when you create your GeoProcessing class, you use the constructor which takes the sevice AND the user credentials. In the background you will receive an access token for the service which is used each time you make a request.
Mark