Just to clear things up as I got stuck on this for about 2 hours. If you need to unlock your phone, make sure you say you are NOT a legit iPhone user. I honestly thought this was a joke and hit yes 3 times, and didn't know why it wasn't unlocking the phone.
And again, if your phone is in DFU mode you will NOT see the connect to iTunes screen, it will just be black! You can do this by, Holding the power button and home button at the same time, count to 10, on 10, release the power button and hold the home button for another 10 seconds. If you did it right, your iphone will be black, and iTunes will prompt you for restore.
@Henry The point of jailbreaking your iphone 3g is not so obvious at the moment, but in the very near future you can expect to see applications use parts of the phone that is not available in the SDK. For example, background processing could be hacked in, but only with a jailbroken phone and many other internal "Apple Only" things could easily be extended once your device is jailbroken.
Also, Why is that I have to fill out 15 field form to write a comment? Email validation is already pushing it. In addition, I did not want to be a part of the newsletter so I unchecked opted out using the checkbox. Upon the submit, I had an error, I quickly fixed it and submit again, before it posted I noticed that the checkbox had defaulted back to checked. Not very nice.