Hi there,
I'm having the same problem too, and I tried the thing sammyz said, but there is no such file in my phone. I used Root Explorer, go into the /system/etc folder, but there was no such folder as init.d. There were just init.goldfish.sh and init.qcom.bt.sh and such.
I'm using a LG-E405 phone with Android 2.3.5, if that helps.
Anyone giving me a hand? I'm exhausted finding compatible .apk files on websites and plug my phone in and put those files in the sd card and setting them up. It just takes too much time. I want to use Google Play T______T
Edit: I aslo tried clearing the cache, data,... even rebooting my phone many times, but nothing worked. I've just bought my phone, and I still couldn't download anything from Google Play yet.