I reset all the data on my iPhone 3GS using the 'Reset all settings and data' option on the iPhone. I never took note of how long the iPhone said it would take to complete. It appears to be processing, although it has been going for over 4 hours. It's a 16GB model, and it was practically full, but still, should it really take this long? Thanks in advance.
Something has definitely gone wrong. See if you can force the phone into recovery mode:
Press and hold the Sleep/Wake and Home buttons at the same time. When your phone turns off, release the Sleep/Wake and Home buttons. Then, leave the USB cable connected to your computer, but NOT your phone, itunes running, press & hold the home button while connecting the USB cable to your dock connector, continue holding the home button until you see “Connect to iTunes” on the screen. You may now release the home button. iTunes should now display that it has detected your phone in recovery mode, if not quit and reopen iTunes. If you still don’t see the recovery message repeat these steps again. iTunes will give you the option to restore from a backup or set up as new. In your case, select "new".