Pode parecer uma pergunta estupida mas como falas em android market, a tua aplicação ainda se chama "android market" ou já esta actualizada para "play store"? A play store vai na versão 3.10.9.
Desde que ele tenha Android 2.2 ou superior fica com a Play Store. O problema aqui é outro meio estranho.Num tlm chinês com android versão antiga isso também passou para play store ? Será que não se ficou pelo market ?