Every app I download from the market, free or paid, gives me this error. I am on Android 4.0.3.
I googled the issue, and there were several results of people having it, on many different phones.
How can I fix this? I have tried clearing cache, data, installing different versions of the market, using WIFI, 3G, etc.