結論
setCookie しようとしている値の domain 属性と path 属性を確認しましょう。
キーが一致していても domain 属性か path 属性が異なっていれば値は上書き・削除できません。
CookieManager
Android アプリで WebView の Cookie を操作したい場合、 android.webkit.CookieManager を使用します。
値の取得は CookieManager#getCookie 、値の変更・追加・削除は CookieManager#setCookie で可能です。
値を削除は HTTP 通信や JavaScript と同様に、 max-age=0 や expires に過去の日付を指定することで行います。
// 値の取得
String cookies = cookieManager.getCookie();
// 値の変更・追加
cookieManager.setCookie(url, "key=value; max-age=3600");
// 値の削除
cookieManager.setCookie(url, "key=; max-age=0");
はまりポイント
CookieManager に限らず、 Cookie は domain 属性と path 属性を持つことができ、ブラウザ（HTTPクライアント）は domain 属性と path 属性を考慮して、実際にサーバに Cookie を送信するかどうかを判断します。
問題は、属性の値を省略した場合の振る舞いです。
domain 属性と path 属性を指定しなかった場合、保存された Cookie はその Cookie を発行した URL の domain と path にマッチする URL へのアクセスに対して Cookie を送信します。
ただし、 domain 属性は明示的に指定した場合と省略した時とでは異なる動作をします。
domain 属性を省略した場合は Cookie を発行したホストに一致する URL へのアクセスに対してのみ Cookie を送信するのに対して、 domain 属性を指定した場合は指定した domain のサブドメインにまで Cookie を送信するのです。
例えば example.com が foo という名前の Cookie を発行したとします。
この時、 Set-Cookie: foo=bar のように domain 属性が指定されていなかった場合、 domain の値は example.com として扱われます。
一方で、 Set-Cookie: foo=bar; domain=example.com と domain 属性を指定されていた場合、 domain の値は .example.com (先頭のドットが大事）として扱われます。
つまり、 domain 属性が指定された Cookie を上書きする際、一見 domain 属性の値が上書きしようとしている Cookie の FQDN と一致しているからといって、 domain 属性を省略すると上書きできません。
Set-Cookie: foo=bar; domain=example.com; path=/
として食わされた Cookie は、 CookieManager から
setCookie("http://example.com/", "foo=; max-age=0; path=/");
としても削除できないのです。
この問題の原因に気づきにくいもう一つの理由
この問題の原因に気づきにくいもう一つの理由は、 CookieManager で取得できる Cookie には各種属性が含まれていないことです。
secure 属性や httponly 属性なんかも見れません。（これらの属性付きで取得する方法をご存じの方がいらっしゃいましたら教えてください。。）
そのため、 domain 属性が異なっていた場合、一見すると値が重複して登録されてしまったかのように見えてしまいます。
cookieManager.setCookie("http://example.com/", "foo=bar; path=/");
cookieManager.setCookie("http://example.com/", "foo=42; domain=example.com; path=/");
Log.d(TAG, cookieManager.getCookie());
// => "foo=bar; foo=42" と表示される
おまけ
CookieManager で Cookie を削除する方法を調べたことがある方なら見たことがあるかもしれませんが、 CookieManager#setCookie の JavaDoc には次のように書かれています。
Sets a cookie for the given URL. Any existing cookie with the same host,
path and name will be replaced with the new cookie. The cookie being set
will be ignored if it is expired.
これだけ見ると、過去の日付を指定しても Cookie 削除されないんじゃ..？と思ってしまいそうです。
しかし、 CookieManager の実装を辿っていった先には、次のように書かれています。
Set cookie for a given url. The old cookie with same host/path/name will
be removed. The new cookie will be added if it is not expired or it does
not have expiration which implies it is session cookie.
一旦削除してから、新しい値を書き込むかどうかを決めるといった感じでしょうか。
有効期限が切れていないまたは指定されていない場合に追加されるのだと理解しておきます。