Solved it. We needed to copy a file into our project.
Instructions if anyone else have this problem:
Copy from this folder where you have your Android SDK:
[YOUR DRIVE LETTER]:\adt-bundle\sdk\platforms\android-23\optional
Name of the file to copy:
org.apache.http.legacy.jar
Copy this file into your project folder at location:
[YOUR PROJECT PATH]\cocos2d\cocos\platform\android\java\libs
Now the project can build with the org.apache.http.legacy.jar file and compilation succeeds.