Android - Problemas en el play store

Muy buenas.
Estoy comenzando a subir apps al play store pero me sucede algo curioso:
Genero mi apk y lo pruebo en mi celular, al darle a un boton me despliega un mapa de google maps y una coordenada predefinida. Me funciona bien.
lo subo al play store y lo descargo y ya no me funciona aparece la actuvity de google maps pero sin ubicacion ni coordenada.
No se como solucionarlo.
Gracias

Pues si quie es raro:
Todo esto lo haces con el mismo movil.

Si, lo pruebo en el mismo celular, y también lo he hecho con otro, mi apk si funciona, pero descargada de google play ya no.
lo unico que he visto es que tengo un GooglePlayServicesUtil.getErrorDialog(status,(Activity)getApplicationContext(),10); que me aparece como deprecated api, alguna idea, gracias

Pues no tengo ni idea:coge la apk que has subido a play store y enviatela por correo a tu dispositivo istalala y prueba .
puede que el apk que has subido no esta actualizada a la que tinen en el id.

si funciona vuelve a generar el apk y vuelve a subirla a play store.

y prueba de nuevo..