I was just unable to enter the right code briefly, after successfully doing so several days ago. Google help suggested I make sure the time on my device was the same as on my computer. Sure enough, today my Palm has drifted about six minutes into the future and after syncing it back to our time, everything was working again.
So swaldman, if you haven't solved this already, maybe you could try temporarily setting the clock on your Pre to show the time that's on your computer. Or you're saying you did that already? I haven't fiddled with any time zone settings, though I know I have them setup correctly for Google Calendar. Can't find where you could setup time zone for your Google Account.