So how did you update Play Services? Or is that Play Store (since the title says one, the message the other, and they are not the same)?
Normally they update silently in the background, but I'm guessing you are manually flashing a gapps package from recovery, or something like that, in which case knowing exactly what you did (step by step), what package you used and what android version you are running might help someone spot what went wrong.