How to fix Samsung Galaxy S Unsuccessful Android Market Download and System Restore Issue
try those steps, I was having this exact problem on my new epic, my first time on an android phone and that's what fixed it for me. I kept hard resetting and entering my info, and it would work for a while then stop until I cleared those specific caches.
I've had a gmail account for a long time but I never use gtalk, I don't know if that's affecting the caching somehow.