(adsbygoogle = window.adsbygoogle || []).push({}); After a lot of digging and work, I finally found a fix which has worked for me on two devices.

1. First, go to settings>applications>manage apps> ALL tab

2. Find these apps. Not every device has all the apps so if you are missing one or two no big deal.

Google Play Store
Download Manager
Google Services Framework
Google Apps (not individual apps. It should specifically say "Google Apps")
Google Talk (or it may just say Talk)
Checkin service

3. Tap each app. Clear its cache and it's data. Do for EVERY APP and DO NOT OPEN STORE UNTIL YOU FINISH THE NEXT STEPS.

4. Now reboot into your recovery menu. Wipe the davlik cache and the regular cache (different with different recoveries)
This will not cause problems with your device.

5. Once you reboot, the device may say it is upgrading. This doesn't mean the firmware version. Let it finish
Don't touch it until it has successfully prepared the SD card and then you should have your home screen running normally.

6. Open the Play Store. This may give you an error. If it does, hit retry. If it gives you the same error, kill it from the task manager and try again.

You SHOULD now be able to download apps again

Tested on my Infuse and brother's Captivate.

I've just registered to say thanks very much. Your fix was the only solution I had working after trying many things. Keep up the good work.

You were the only person to reply after 5000 views. Thank you very much for doing so and I'm glad I helped fix your problem.