For the people that have problems with the new iPhone IOS4 software, I found something that work:
Download the iPhone configuration utility at:
http://support.apple.com/kb/DL926?viewlocale=en_US
and create a new configuration profile and fill only the advanced setting for network access (first field). In this field, put your operator access adress, for Swisscom Switzerland, I filled: GPRS.SWISSCOM.CH
and load the profile to the iPhone.
Good luck
iPhone 3Gs 32Mo iOS 4 Operator Swisscom