AndroidからNokiaのOAuth1.0認証

現在AndroidからNokiaAPIのOAuth認証がしたいと思い、以下のアプローチでOAuth認証に取り組んでおります。
1, URIを使用し、必要パラメータを挿入して認証URLを生成
2, URLを内蔵ブラウザに飛ばした後、コールバックURLからアプリを起動
3, onResumeでIntentからデータを受け取り、tokenを使ってユーザー認証URLを生成

現在この手順の2で詰まっております。
認証URLを生成してブラウザに飛ばすことは出来ているのですが、Invalid Signatureが帰ってきてしまい、Tokenを取得することが出来ません。
Signature生成のアルゴリズムに関しては公式のコンソールにある値を入れてみて正常なSignatureを生成することができたので問題はありません。

以下認証URL生成部分のコードです。

Java
1    private Uri buildRequestTokenUri() {
2        Uri.Builder builer = Uri.parse(API_REQUEST_TOKEN_URL).buildUpon()
3                .appendQueryParameter("oauth_callback", API_OAUTH_REDIRECT)
4                .appendQueryParameter("oauth_consumer_key", API_OAUTH_KEY)
5                .appendQueryParameter("oauth_nonce", UUID.randomUUID().toString())
6                .appendQueryParameter("oauth_signature_method", "HMAC-SHA1")
7                .appendQueryParameter("oauth_timestamp", Long.toString(System.currentTimeMillis() / 1000L))
8                .appendQueryParameter("oauth_version", "1.0");
9
10        String url = URLEncoder.encode(API_REQUEST_TOKEN_URL);
11        String queries = URLEncoder.encode(builer.build().getQuery());
12
13        String baseString = "GET&" + url + "&" + queries;
14        String signature = "";
15        try {
16            signature = URLEncoder.encode((hmacSha1(baseString, API_OAUTH_SECRET + "&")).trim());
17        } catch (UnsupportedEncodingException | NoSuchAlgorithmException | InvalidKeyException e) {
18            e.printStackTrace();
19        }
20
21        builer.appendQueryParameter("oauth_signature", signature);
22        Log.d("signature", signature);
23
24        return builer.build();
25    }
26
27    private static String hmacSha1(String value, String key)
28            throws UnsupportedEncodingException, NoSuchAlgorithmException,
29            InvalidKeyException {
30        String type = "HmacSHA1";
31        SecretKeySpec secret = new SecretKeySpec(key.getBytes(), type);
32        Mac mac = Mac.getInstance(type);
33        mac.init(secret);
34        byte[] bytes = mac.doFinal(value.getBytes("UTF-8"));
35
36        return new String(Base64.encodeToString(bytes, 0));
37    }