I had very occasional random restarts with my D3 - once a month at most - until I received the over the air update to 906 in May, and it has only happened once since.
It's possible that it's the battery - perhaps the terminal connections are bad? If you've tried a new phone and battery, it's probably not that, though. Since you have so few apps on the replacement phone it's probably not an app.
Try calling for a new handset (ask them to send a battery as well, in order to rule that out.)