Wow. I have pretty much religiously upgraded to every firmware release that has come out post version 2.0 since becoming a 3G owner on release-day last year. And I was happy enough with 3.0 performance on my 3G phone when it came out, and have been ecstatic about its performance on my new 3GS.
But with this report about the random but frequent blackouts/freezes as well as the other prolific threads about atrocious battery life, combined with all of the issues surrounding jailbreaking on the 3GS and the fact that 3.1 just isn't really that compelling of an upgrade for me personally anyway, and what you've got is me seriously contemplating, for the very first time, sitting this one out.
One thing I have noticed, though, when trying to find a common thread amongst those people who are experiencing this issue, is that we have eliminated both Mobile Me and Exchange email as culprits (edit: as well as wifi?), but as far as I can tell (and I perhaps should go through each post individually again to make sure that this pattern holds), there isn't one person having the lockup issue who doesn't have at least one program authorized to provide push notifications. Perhaps the issue lies there? Maybe it is sometimes locking up instead of doing the right thing when a push message comes through?
For those experiencing the problem, maybe try turning off push notifications entirely for a day, and hold off on doing another firmware restore or iPhone exchange at the Genius Bar just to see if turning off push by itself does the trick.
-- Nathan
EDIT: Well, scratch that idea, I guess? Found a post by OP saying he had push disabled for all apps, although he was still using it for Mobile Me email. Has anybody turned it off all across the board (every email account, calendaring, contacts, all push notifications from all apps, etc.)?