Authentication Error when using HttpPost with DefaultHttpClient on Android

I'm running into a strange problem using HttpClient. I am using a DefaultHttpClient() with HttpPost. I was using HttpGet with 100% success but now trying to switch to HttpPost as the REST API I'm using wants POST parameters rather than GET. (Only for some API calls though so I know that the GET calls were working fine so it's not a fault of the API).

Also, I tried using HttpPost on a simple php script I wrote that looks for a POST parameter 'var' and echoes it to screen, passing this parameters as follows worked fine:

List<NameValuePair> nameValuePairs = new ArrayList<NameValuePair>();

    postMethod = new HttpPost("http://www.examplewebsite.com");

    nameValuePairs.add(new BasicNameValuePair("var", "lol"));

    try {
        postMethod.setEntity(new UrlEncodedFormEntity(nameValuePairs));

        response = httpClient.execute(postMethod, responseHandler);
        Log.i("RESTMethod", response);
...

The problem is that when I tried and do the same call to the API (but with the params changed to the API params obviously) I get the following error:

Authentication error: Unable to respond to any of these challenges: {}

The page I am requesting is an HTTPS page, could this be the problem?

But doing the same type of POST request to a raw HTTP page on the API gives the same error, unless I comment out the StringEntity part and then it runs (but returns xml and I want to pass a parameter to request the data in JSON).

This seems like a really strange problem (the non-https part) but couldn't really find any help on this problem so sorry if the answer is out there.

Any ideas?

Thanks in advance,

Infinitifzz

EDIT: Okay I'm getting nowhere so I thought if I directed you to the API it might shed some light, it's the 8Tracks API and as you can see you need to pass a dev key (api_key) for all r