It is highly recommended you restore your iPhone before proceeding and attempting the jailbreakme.com method, even if it is brand new, just updated, etc. Users report they did not succeed the first time on their brand new or just virginized upgrade 1.1.1 iPhones. But after a restore, it worked. So to save some time, just follow this guide and RESTORE NOW.
Download 1.02 Firmware
Download 1.1.1 Firmware
1) Connect your iPhone to your computer via the USB cable and make sure you have updated to the latest version of iTunes. Download the 1.1.1 restore file above. Go into iTunes and sync your phone for a fresh backup of your phone, if this phone is brand new, skip this.
2) Hold down the Top Power Button and the Front Menu Button for about 15-30 seconds, your phone will reboot a few times during this, ignore it and keep holding it down until you see a yellow ! symbol and it asks you to connect to iTunes.
3) Open iTunes if it is not already open, iTunes will tell you that it has detected an iPhone in restore mode and you must restore it before continue.
4) Hold down SHIFT key (Windows) or Option/ALT-key (Mac) when clicking the Restore button, and select the 1.1.1 file you downloaded in step 1 and it will restore with the latest firmware. After completing (~10 minutes), your phone should be fully restored and you can continue to jailbreak, if you wish.
Note: After successfully jailbreaking and activating your iPhone, the next time you connect to iTunes, it should ask you to restore that latest backup. Your backup contains all your contacts, settings, call times, etc. But not your camera roll, so back that up, always