I was successfully running the new Chartboost sample app on my android phone today. I had to install the Google Play Services via the Android SDK Manager as explained here. I then had to change the API level to android-21 in step 3 to match the API installed in the SDK Manager. In step 4 i edited the ChartboostSample/android/project.properties to also match the API level.
Now it works and the problems I had before are gone. Next step will be to integrate the new Chartboost into my own game.