Just as a follow up. I have managed to upgrade my iphone (3G, O2 UK network locked) using a MacBook Black, on iTunes 9.2.1. This is how:-
1. Sync Phone and backup contacts
2. Download iphone OS 4.0.1 (iPod, iPhone and iPad Firmware Download). YOU MUST DO THIS AS THE OS 4.0.2 CAN'T BE JAILBROKEN AT THIS TIME.
3. Insert old O2 sim card into iphone, connect with computer
4. Click on "Restore" in iTunes holding down the option key, select the iphone firmware you downloaded earlier. YOU MUST DO THIS AS THE OS 4.0.2 CAN'T BE JAILBROKEN AT THIS TIME.
5. Let apple do its magic
6. Ignore carrier settings upgrade invite for now
7. Go to network settings and connect to your wireless network
8. In the iphone safari, go to jailbreakme . com follow the instructions
9. Once jailbroken, go to cydia and install ultrasn0w
10. During the reboot, change your SIM card to your normal one
11. Ater the restart, allow for the carrier settings upgrade to be installed (It installed CSL not O2)
12. Do a full sync to get your tunes, contacts etc back on the phone.
After having done this I had the bonus of the GPRS finally working properly!