cocos2dxのAndroidのビルドをbuild_native.shでするとき、全ソースコンパイルし直したいときは、cocos2dx以下のAndroid.mkの日付をtouchコマンドなどで変更すると良いでしょう。
touch cocos2dx/Android.mk
makeファイルは作成したファイルと元のファイルの日付でコンパイルやリンクの判断しているので、ソースやライブラリを追加しても、その日付が古いとコンパイルし直されないときがあります。ダウンロードした圧縮ファイルを解凍して追加した場合はそういうことが起こりえます。
普通は中間ファイルを消すcleanというオプションがある事が多いのですが、build_native.shの中には見あたりません。なので、追加したファイルの日付を変えるか、もしくは「.mk」ファイルの日付を変えるとコンパイルし直されます。
touchコマンドは引数に指定したファイルが存在しないときは空ファイルを作り、指定した場合はコマンド実行時の日付にそのファイルの日付を変えるコマンドです。