Something has gone wrong. On an iPhone 4, the erase all data & settings, should happen almost instantaneously as all that's really deleted is the hardware encryption key.
Turn the phone off using the Sleep/Wake button, then the slide to power off. If you are unable to do that, 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".