Can't connect to iPod: iTunes claims iPod Touch needs passcode entered

I have the solution for you here.

1. Plug the iPod into iTunes
2. Hold the power and home button together until the screen goes black
3. Let go of the power button, keeping home pressed
4. after 10 seconds let go.
5. open iTunes and click restore iPod.

you have a blank iPod, and will need to sync again

Update (from original poster)

These steps are correct, I had to actually go to the Genius Bar to find that out because the instructions on Apples own site are not correct. Specifically they do not recommend the two-button shutdown, but rather a regular shutdown which does not work.

More details here: http://codesweattears.blogspot.com/2011/12/putting-your-ipod-touch-into-recovery.html