Re-installed Play Store doesn't work
Ensure that the Google Play store is installed as a system application.

Once done, clear the data for the Google Play store, the Google Play Services and the Google Services Framework apps.

Open the Google Play Store (you will get an error, don't worry!).

Reboot, and open the gTalk app. Log in to your gTalk account using the gTalk application (you may have to do it a few times, wait until it says you're online).

Reboot and open the Google Play store again :)