I have the same trouble. I don't really do apps, so there are none to speak of on my phone, it's been doing it since I bought it. It is fully upgraded as far as I know and it seems to auto-restart when I am trying to text than at any other time. But on occasion it will do it when just sitting idle. It seems to take almost a min or two to fully reboot.
I have done several factory restores and no change, I reported it when it was under warranty and they did nothing. It is really getting annoying as I also use the phone to run my business and when it shuts off in the middle of a call it costs me money.
I have the motorola milestone.It's a POS.