Have you, by any chance, rooted the phone? If so, and are using a custom ROM, this could be the cause. Some of them do not come with any Google services and to fix this you need to flash aGApps using programs such as say 'Clock Work Mod'.
If you have already flashed and this is still happening, this could be caused by flashing an incompatible GApps package and you will need to get the correct one.
If that isn't the case (and you are positive that you have the correct/compatible GApps installed), try the following:
1. Open your "Google Play" app and press the "Home button". (Do not close the "Google Play" app.)
2. Next go to "Settings", then tap "Applications" and then "Manage Applications".
3. Select the "ALL" tab, and search/scroll...