Stiamo parlando di server HTTP/CGI che non dialoga con il browser di default di Android? Puoi postare una sessione HTTP di esempio, per vedere se il server C agisce correttamente? Provando con vari browser (Firefox, Chrome, Opera, ...) funziona o dà gli stessi problemi di Android?

---edit---
Leggendo in giro pare che il browser di Android non implementi perfettamente lo schema digest.
Inoltre, tieni presente che comunque non è il massimo dal punto di vista della sicurezza (tutto il resto del traffico passa comunque in chiaro), per cui una soluzione decisamente più sicura sarebbe passare su HTTPS.