Samsung Galaxy S4 — Problema con google

Hola, escribo por este medio por qué no e encontrado un problema similar en la página o alguno que solucione este problema, me disculpo de ante mano si no es lugar indicado.
Les cuento mi situacion, tengo un S4 con Android 5.0.1 original de fábrica y todo me andaba muy bien, hasta que lo abandone hace un mes más o menos por qué la batería estaba muerta lo seguía usando de vez en cuando pero enchufado por que presentaba el problema que solo me cargaba con ciertos cargadores o enchufado solamente en la pc ( no sé si sería un problema de voltaje). Cuando le compré una batería nueva y se la puse ya me pareció raro que no pude entrar al play store para descargarle nuevamente whatsapp. Y se me trababa y se cerraba YouTube cuando queria entrar, entonces opte por hacerle un Factory reset y para mí sorpresa no funcionan las apps de google, no se actualiza Google Play service por lo tanto cuando abro el play store automáticamente se cierra y así con las Google apps. Probe dejarlo toda una noche encendido con conexión a internet a ver qué sucedía y nada , mi último intento fue forzarle la actualización de GPservice y para mí sorpresa me apareció un cartel que decía : Google Play service no se ejecutará hasta que no actualice los servicios de Google Play, ahí fue donde me di cuenta que algo muy raro pasaba. Mi pregunta es si alguno le pasó alguna vez y conoce la solución que me informe por favor. Y si puede llegar a ser algún problema por parte de la batería nueva (que pienso yo que sería una locura).

Gracias de antemano