Android以外のJava実装と、AndroidでのJavaの実装では、
正規表現クラス(java.util.regex.*あたり)の実装が異なっています。
Qiita上にも記事があるようです。
そこに書いていない、自分の引っかかったポイントを1つ紹介します。

課題

タイトル通り、
AndroidのMatcherでは与えられたCharSequenceをtoString()したものを処理する という点です。
Javaでは、toString()は行わず、そのまま処理されます。

これによって起こる問題

Matcherに文字を渡す際(Pattern#matcher(str),Matcher#reset(str))、Stringを渡すならどうってことありません。
しかし、StringBuilderやStringBufferを、同じ動作と思って渡すと痛い目に遭います。

それぞれでの書き方の例

正規表現APIを大して使う必要がないサンプルですが、どうかお気になさらず。
StringBuilderの中に入った文字列のcをdに置き換える場合。

共通部分

StringBuilder sb=new StringBuilder("abccabc abc abc abc abc");
Matcher m=Pattern.compile("c").matcher(sb);

Android以外の場合

int start = 0;
while(m.find(start)){
    sb.replace(m.start(), m.end(), "d");
    start = m.start();
}

Androidの場合

int minoff = 0;
while(m.find()){
    sb.replace(m.start() - minoff, m.end() - minoff, "d");
    minoff += m.end() - m.start(); // <- ( このサンプルでは常に += 1 )
}

独り言

~~Androidでの実装、toString()されると遅くなっちゃうんだよな。~~
JNIで処理してくれるので多分そんなこともない。