First authenticated request to server always fails

Question

When trying to access a server that's secured with basic authentication, my first request always fails, but the second succeeds with the same credentials.

Here is the relevant method:

// username and password are entered by the user, the serviceurl is the endpoint on the server
private boolean testHttpLogin(String username, String password, String serviceUrl) {
  if (username != null && username.length() > 0 && password != null && password.length() > 0) {
    try {
        Response<String> serverResponse = null;
        serverResponse = Ion.with(getApplicationContext()).load(serviceUrl).noCache()
                            .basicAuthentication(username, password)
                            .asString().withResponse().get();
        logger.debug("response in testLogin: " + serverResponse.getResult());
        int responseCode = serverResponse.getHeaders().code();
        if (responseCode != HttpURLConnection.HTTP_UNAUTHORIZED) {
            taskUserName = username;
            taskPassword = password;
            logger.info("Login successful!");
            return true;
        } else {
            logger.info("Login failed!");
            BasisUtils.showToast("User not authorized!");
        }
    } 
    catch (ExecutionException | InterruptedException e) {
        [...] // handle exceptions...   
    }       
    return false;
  }
}

So when the user tries to log in, the first time it'll come back as 'not authorized' and when he tries a second time (without changing any input), it works.

Things I already tried:

• Sending an unauthenticated request first and the authenticated second
• Sending an authenticated request with wrong credentials first
• wait for half a second before sending 2nd request
• enabling/disabling caching with Ion

The response headers of the first request are as follows:

Date: Fri, 12 Jun 2015 13:00:00 GMT 
Server: Apache
WWW-Authenticate: Basic realm="somerealm"
Content-Length: 381
Keep-Alive: timeout=15, max=100
Connection: Keep-Alive
Content-Type: text/html; charset=iso-8859-1

The headers from a successful login look like this:

date: Fri, 12 Jun 2015 14:28:15
server: Apache
x-powered-by: ASP.NET
x-aspnet-version: 2.0.50727
x-xss-protection: 1; mode=block
x-frame-options: SAMEORIGIN
cache-control: private, must-revalidate, max-age=0
content-type: text/html;charset=utf-8
set-cookie:[the token I need]; Expires=Fri, 12-Jun-2015 14:29:12 GMT; Path=/path/on/server; HttpOnly
vary: Accept-Encoding
content-encoding: gzip
content-length: 1689
keep-alive: timeout=15, max=98

Update

The request headers look like this:

Host: mobile.myserver.com:4434
User-Agent: Dalvik/1.6.0 (Linux; U; Android 4.1.2; GT-P5100 Build/JZO54K)
Accept-Encoding: gzip, deflate
Connection: keep-alive
Accept: */*
Cache-Control: no-cache
Authorization: Basic dXNlcm5hbWU6cGFzc3dvcmQ= // exchanged the real credentials against username:password

They are the same for both requests.

Looking at the headers today I noticed that there was a cookie included in the headers from a prior connection to the server (I have to check the authentication method on the server before the user logs in). I now remove all cookies before making the request (just in case the cookie isn't valid for the request):

Ion.getDefault(getApplicationContext()).getCookieMiddleware().getCookieStore().removeAll();
serverResponse = Ion.with(getApplicationContext()).load(serviceUrl).noCache()
                    .setLogging("ION VERBOSE", Log.VERBOSE).basicAuthentication(username, password)
                    .asString().withResponse().get();

I just looked a bit further and it gets more confusing. Apparently, the second request doesn't even have to be in the same "app session" (i.e. I can force stop the app via settings, reopen it and the request will still succeed).