Я думаю, что это как-то связано с конфликтами имен внутри библиотек Android.
Я скопировал исходный код Java Base64 в свой проект в пространство имен org.apache.commons.codec.binary. Проект скомпилирован без проблем. Однако во время выполнения в симуляторе Android у меня была та же ошибка, java.lang.NoSuchMethodError: org.apache.commons.codec.binary.Base64.encodeBase64String.
Однако после того, как я изменил пространство имен на com.apache.commons.codec.binary вместо org, приложение работает как по волшебству. Я предполагаю, что в реализации Android используется org.apache.commons.codec.binary, и это не позволяет вам снова использовать его в своем коде.