I went through this for a while as well after the update to 1.1.2. I eventually called support after an unusually bad day of rebooting over and over again (I'm talking about hours of rebooting). Support had me restore and reflash the phone and about an hour later it was back to its old tricks and the rebooting started again. The second call to support brought more action -- either wait for a new box and phone to show up or go to the Genius Bar. I chose the latter.
At the Genius Bar they basically checked that I had done all of the stuff (of course the phone wasn't rebooting then but I had brought a 10 minute video of it with me in case), charged the phone, etc. After that, they handed me a "new" one from a white box... probably a refurb. I haven't had the problem since. All-in-all it was a very pleasant process considering what customer service can be like these days.
