Boo. Really had to factory reset? I just setup phone how I liked it. O and wow for type lag. There's none. Way faster than my xoom.. like g the phone so far!
Just had same problem as OP....:( Factoryreset did the trick when nothing else did.
One other thing to check for anyone having this issue: go to Accounts under your main Settings (press Menu from the home screen). Select your Google account and make sure GMail is set to synch.