ビルドターゲットをAndroid6（APIレベル23）の状態のまま対応する方法です。
エラーの原因はorg.apache.http.Headerとorg.apache.http.message.BasicHeaderが存在しないため発生しています。
これらのクラスはapacheが提供しているクラスで、Android5.1.1まではandroid.jarの中に同梱されていました。
しかし、Android6.0になったタイミングでapacheのクラスは必要最低限のものしか格納されていません。
Cocos2d-xのライブラリはそれに対応されていないため、自分で対応する必要があります。
対応といってもCocos2dxDownloader.javaを書き換えることはしません。
足りないものを追加するだけです。
org.apache.http.Headerとorg.apache.http.message.BasicHeaderはapacheのHttpCoreライブラリに入っているので
下記のサイトからHttpCoreをダウンロードします。
HttpClientも動作に必要になると思われるので一緒にダウンロードしてください。
http://hc.apache.org/downloads.cgi
（※2016/01/27時点のバージョンはHttpCoreは4.4.4でHttpClientは4.5.1）
ダウンロードしたファイルの中にあるhttpcore-4.4.4.jarとhttpclient-4.5.1.jarを下記の場所に配置。
■プロジェクトの言語が、C++の場合
(※ cocos new TestApp -p com.name.cocos2dx.testapp -l cpp -d xxxxxx このコマンドで、プロジェクトを作成した場合)
[../プロジェクト/cocos2d/cocos/platform/android/java/libs]
■プロジェクトの言語が、JavaScriptの場合
(※ cocos new TestApp -p com.name.cocos2dx.testapp -l js -d xxxxxx このコマンドで、プロジェクトを作成した場合)
[../プロジェクト\frameworks\cocos2d-x\cocos\platform\android\java\libs]