You may need to "jailbreak" and unlock the iPhone. If this is an iPhone 2G (the original model), you can follow this guide: http://www.ihackintosh.com/2010/02/jailb...
If you have an iPhone 3G or 3GS and you updated to iOS 4.0.1, then you can visit the website (using your iPhone): jailbreakme.com. After jailbreaking, you then select the Cydia app and search for and install "ultrasn0w" (note the 0 is a zero).
If you updated to 4.0.2 or later, then you are stuck until a new jailbreak method is revealed.
If you have an unlocked or jailbroken iPhone, you should never let iTunes update your phone. You need to research first and find out if there is a safe way to update for any new iOS version.