just had this problem on my galaxy S3. I had two little warning signs saying there were errors updating "samsung push notifications" and Facebook. the Google Play store was showing error 500 when I tried to update.
Until I opened the Samsung Apps, which automatically updated my push notifications, and then right after Google play started working
not sure about other devices but it worked for me