Error "HTTP/1.1 401 Unauthorized" with basic authentication in android - EWS 2010

Question

I refer to this link to request to the server. The problem is sometime (not always, about 20% - 30%, means sometime I can get successful response), I got the 401 error and server response basic authorization challenge expected, but not found.

Here is my code:

 HttpRequestInterceptor preemptiveAuth = new HttpRequestInterceptor()
{
    public void process(final HttpRequest request, final HttpContext context)
            throws HttpException, IOException
    {
        AuthState authState = (AuthState) context
                .getAttribute(ClientContext.TARGET_AUTH_STATE);
        CredentialsProvider credsProvider = (CredentialsProvider) context
                .getAttribute(ClientContext.CREDS_PROVIDER);
        HttpHost targetHost = (HttpHost) context
                .getAttribute(ExecutionContext.HTTP_TARGET_HOST);

        if (authState.getAuthScheme() == null)
        {
            AuthScope authScope = new AuthScope(targetHost.getHostName(),
                    targetHost.getPort());
            Credentials creds = credsProvider.getCredentials(authScope);
            if (creds != null)
            {
                authState.setAuthScheme(new BasicScheme());
                authState.setCredentials(creds);
            }
        }
    }
};

Here is my authentication:

    HttpPost httpPost = new HttpPost(SERVER_AUTH_URL);
        httpPost.setHeader("Content-type", "text/xml; charset=utf-8");
    httpPost.setHeader("Keep-Alive", "300");
    httpPost.setHeader("Connection", "Keep-Alive");     
    StringEntity se = new StringEntity(myRequest, "UTF-8");
    httpPost.setEntity(se);
    se.setContentType("text/xml");
    se.setContentEncoding("gzip,deflate");

        //add preemptiveAuth
        client.addRequestInterceptor(preemptiveAuth, 0);
        //Set the proxy
    ProxySelectorRoutePlanner routePlanner = new ProxySelectorRoutePlanner(
            client.getConnectionManager().getSchemeRegistry(),
            ProxySelector.getDefault());
    client.setRoutePlanner(routePlanner);

    List<String> authPrefs = new ArrayList<String>();
    authPrefs.add(AuthPolicy.BASIC);
    authPrefs.add(AuthPolicy.NTLM);
    authPrefs.add(AuthPolicy.DIGEST);
    client.getParams().setParameter("http.auth.scheme-priority", authPrefs);
    CredentialsProvider credProvider = new BasicCredentialsProvider();                 
    // client.getParams().setParameter("http.auth.scheme-priority",
    // authPrefs);
    credProvider.setCredentials(AuthScope.ANY,
            new NTCredentials(getUsername(), getPassword(),
                    "", getDomain()));

    Log.d(TAG, "repair excute");
    client.setCredentialsProvider(credProvider);
    HttpResponse response = client.execute(httpPost);
    Log.d(TAG, "has excute");

From the comment code, you can see I tried many ways, but the error wasn't disappear. Here is logcat say:

 05-02 10:28:21.724: D/dalvikvm(1169): GC_FOR_MALLOC freed 11259 objects / 457352 bytes in 43ms
 05-02 10:28:22.384: D/MainActivity(1169): repair excute
 05-02 10:28:22.744: D/dalvikvm(1169): GC_FOR_MALLOC freed 11481 objects / 447264 bytes in 67ms
 05-02 10:28:22.894: D/dalvikvm(1169): GC_FOR_MALLOC freed 1078 objects / 83928 bytes in 76ms
 05-02 10:28:22.894: I/dalvikvm-heap(1169): Grow heap (frag case) to 3.833MB for 87396-byte allocation
 05-02 10:28:23.034: D/dalvikvm(1169): GC_FOR_MALLOC freed 58 objects / 3336 bytes in 143ms
 05-02 10:28:23.124: W/DefaultRequestDirector(1169): Authentication error: basic authorization challenge expected, but not found
 05-02 10:28:23.124: D/MainActivity(1169): has excute
 05-02 10:28:23.124: E/MainActivity(1169): response error: HTTP/1.1 401 Unauthorized

So, please tell me where is my problem. Thanks in advance.
Update: the target server is Exchange Web Service 2010. For some reason, I don't want to use EWS API, I made my own xml request to connect to the server (this xml request works properly).
And here is the response header from server When request failed:

Server   Microsoft-IIS/7.5
WWW-Authenticate   Negotiate
WWW-Authenticate   NTLM
X-Powered-By   ASP.NET
Date   Fri, 25 May 2012 03:47:57 GMT
Content-Length   0

When request success the first time:

Cache-Control   private
Transfer-Encoding   chunked
Content-Type   text/xml; charset=utf-8
Server   Microsoft-IIS/7.5
Set-Cookie   exchangecookie=1d9d9b1d21064035ad375c8aecde2168; expires=Sat, 25-May-2013     04:00:46 GMT; path=/; HttpOnly
X-AspNet-Version   2.0.50727
X-Powered-By   ASP.NET
Date   Fri, 25 May 2012 04:00:45 GMT

and the second time:

Cache-Control   private
Transfer-Encoding   chunked
Content-Type   text/xml; charset=utf-8
Server   Microsoft-IIS/7.5
X-EwsPerformanceData   RpcC=4;RpcL=0;LdapC=0;LdapL=0;
X-AspNet-Version   2.0.50727
X-Powered-By   ASP.NET
Date   Fri, 25 May 2012 04:00:47 GMT

The cookie is my problem, isn't it?

Answer 1

I was struggling with Android HTTP basic last week. I have tried maybe 3 or 4 different ways of doing it and always I found some problem. Right now the only way I managed to make it work was the simplest way.

 UsernamePasswordCredentials credentials = new UsernamePasswordCredentials(user, pass);
 Header header = new BasicScheme().authenticate(credentials, mHttpRequest);
 mHttpRequest.addHeader(header);

That worked for me with AndroidHttpClient.

Edit:

This is my full source code

https://gist.github.com/2642692

It's based on http://lukencode.com/2010/04/27/calling-web-services-in-android-using-httpclient/