Just following up on my comment that lead to your solution.
In most cases, I find that when the base64-encoded String in the Auth header is invalid, servers tend to behave strangely. So verify that the Authorization Header is correct.
In general, it's always best to try these kinds of things with curl first. The following is an example command with curl
curl -X POST -H "Authorization: Basic <base64-encoded String>" http://some.server.url.com/some-endpoint
I see you added trim() to fix it. The real solution is to use Base64.NO_WRAP (http://developer.android.com/reference/android/util/Base64.html#NO_WRAP). So you want to do this when encoding:
Base64.encodeToString( APP_STRING.getBytes() , Base64.NO_WRAP );
I should have probably noticed that the first time around but either way, I'm glad my first thought lead to your answer :-)