I also tried all suggestions provided by Apple and kept getting the same results:
"ITunes could not connect to the ipod touch because it is locked with a passcode. You must put the passcode on the ipod before it can be used with itunes"
After multiple tries this is what worked for me:
1) Completely turned off ipod while connected to iTunes.
2) Held home button down AND USB plug at EXACTLY the same time until the USB cable and iTunes picture appears on the ipod.
3) iTunes showed the restore option
4) Performed full restore
It took me like 5 tries to get this thing working. Hope this helps.