I am having the same problem on the HTC Magic.
I have also tried the suggestions listed:
(Have powered down and back on.
Have powered down, battery out, back in, back on.
Have done above plus removed and replaced SIM.
Have cleared market cache.
Have cleared cache, powered off and back on.
Have logged into Google Talk, back out and back in again.)
And also, I have checked the time zone and date, which are correct.
I did install, try, and then uninstall Dolphin shortly before this, without ever setting it to be the default browser.
I am desperate to avoid a hard reset - it took me hours of faffing about to get all the settings right.
Any other suggestions out there?