サーバーの署名ベースを oauth に一致させる必要があります。これは、署名する前にすべてをパーセントでエンコードします。
Urlencoder.encode( base, UTF-8) ではなく Uri.encode を使用すると、空白と + が正しくエンコードされますが、予約されていない文字 ("_-!.~'()*") もエンコードする必要があります。
それらのために独自のユーティリティを作成するのはそれほど難しくありませんが、手動で変更する必要がなければいいでしょう。これにはすでにユーティリティがありますか?