I have a 16GB iPhone 3G with Fetch set on 15 minutes. I don't have 3G where I live so I never have 3G enabled. It also doesn't matter if I am connected to wifi or using data, I still have the problem. Like I said I have tried multiple restores and nothing has changed.
I also have problems with GPS. Sometimes I never can get the blue dot and sometimes it takes a while to get the crosshairs even in full service.