I had the same problem with AT&T while visiting south Florida in late October from my home base in Canada on the Rogers network. It had worked fine in Canada onRogers for over amonth with no problems. Within minutes of turning on the Bold in the US it constantly rebooted. I solved the problem while in the US by enabling 2g only, something which is offered on Rogers' Bolds, but I understand is not available on AT&T Bolds because of a firmware block. While in Florida the Rogers rep advised me to upgrade the OS to .162 which he said would solve the problem. As I was afraid of possibly loosing my BES e-mail, which was critical while I was away, I did not upgrade the OS until I got back to Canada (where I never had the rebooting problem) so cannot say if that will solve your problem. All I know is that my rebotting problem was only while on 3g and on the AT&T network.
I have been running .190 for a month and a half on the Roger's network with absolutely no problems. I have not been to the US since I had the problem, so cannot say for sure if the problem can be solved with your phone with an OS upgrade. I tried the official AT&T .167 for a week, with no issues, except I found that it used more memory after a while. .185 and .190 both worked fine for me, with more available memory than .167. I would highly recommend .190 (the latest official OS) which seems to have been out longer than any other official OS before being replaced.
I agree, however, if it is a new phone, get it replaced. You should not have these problems. It should work out of the box!!!