Boot it into Recovery Mode.
Download iFuntastic or iPhuc (iFuntastic - Mac OS X, iPhuc - Windows)
In iFuntastic, click Exit Recovery Mode / Restart Device.
Device will boot
Connect to iTunes. Restore. or just restore from Recovery if it is truly stuck.
In iPhuc, open it up by 'cd' to the folder where you extracted it.
type in the command prompt "cmd fsboot" and the iPod should reboot into Normal Mode. Then restore with iTunes.
If iPhuc doesn't work for you, simple put it in Recovery and restore with iTunes.
To put the device in Recovery Mode:
Hold the Sleep/Wake and Home buttons. Ignore the red slider that appears.
When the Apple Logo appears, let go of the Sleep/Wake Button but keep holding the Home Button.
When the Connect to iTunes image appears, let go of the home button and iTunes will tell you that it has detected an iPod/iPhone in recovery mode.
Then the restore should work.
If iFuntastic doesn't work. Download iNdependence for Mac OS X and open it with the iPod in Recovery. The app will slap the iPod/iPhone out of Stupid Mode and into Awesome Mode it is always in.
Cheers!!!!