I turned off Notifications and still had the problem occur.
I've returned my phone for a new one four times... the last one was three days ago. Yes, I'm on my 5th iPhone in less than two months of making the purchase. I will keep returning it until the problem's fixed or if I just can't take it any more or Apple goes out of business. If you own Apple stock, it's time to sell!
The last phone failure occured with the following:
1) The phone failed after three to six days of being activated, just like the others.
2) Otter Box screen protector ripped out (no screen protector at all)
3) No downloaded applications
4) Did not change the ring tones
5) Did not connect to my PC via cable connection
6) Took a few pictures
7) Moved icons around on the iPhone to clean up the display.
8) Set up e-mail account via Microsoft Exchange
9) Set up ActiveSync with Outlook
10) Sync'd in the Contacts, E-mail, and Calendar
11) Set up iPhone to Fetch data instead of Push (as a test). Had Notifications turned off.
12) Made a dozen or so phone calls
13) Received a dozen or so calls
Note: On my current (5th) iPhone-4 I also had a new sim card installed. Also found out that iTunes was duplicating a whole bunch of shortcuts on my PC. I uninstalled itunes thinking that maybe the shortcut garbage was being sent to the iPhone via Microsoft Exchange.