si, può provare a disinstallarlo (magari con titanium backup) e poi reinstallarlo... scaricalo da qui [APK] Google Play Store 4.5.10 - xda-developers
se non dovesse funzionare penso che la cosa migliore sia il flash della rom.
Una cosa... ma hai provato ad aggiornare la rom dalle impostazioni? magari il flash di una nuova nightly te lo sistema