I had the same problem after a factory reset. I googled 'android market apk' and found it right away. Just click on the apk and let it roll. Your new market will be up and running in no time. Hope this helps
I had the same problem & has done all of this. Stil;l having the same problems...my phone will not download apps from the "green" market nor the new 'android market apk'. I "let it roll" but still says ERROR!!!!! Help me someone