Share your experience!
Settings > apps > all> play store > clear data > restart the phone > check again
After following the advice from uliwooly, open this link in your phone and select the option to open it using Play Store: https://play.google.com/store/apps/details?id=com.google.android.gms&hl=en.
It will only clear data for the play store app. It will not affect your other apps, data and Google account.
Which version do you have of Google Play Services if you tap it under Settings -> Apps? Where do you get a message that's saying it's outdated? Is it when you open a certain app?
I tested this here on a Xperia M2 with the latest software and the latest version of Google Play Services is 8.4.89. I would not recommend that you try to download Google Play Services from any 3:rd party source. As i understand it, Google has different versions of this app depending on phone and perhaps also market.
Try to disable Google Play Services under Settings -> Apps and then enable it again and see if that helps. If not, are you able to use for example Hangouts in the phone? Perhaps the message you see is because of an app you've downloaded and not because of Google Play Services.