This happened to me as well, took me 3 days to fix it but with the help of others I got it.
1. Find a second computer, install iTunes if it is not installed
2. Connect iPod Touch in normal mode, Firmware 1.1.4, non-restored
3. Authorize iTunes on computer 2 using your apple ID
4. Copied paid copy of Firmware 2.0 from computer 1 to USB stick, transferred to computer 2 (necessary because despite account authorization, iTunes wanted to sell me Firmware 2.0 again!) Find this by going to C:\Documents and Settings[user profile name]\Application Data\Apple Computer\iTunes\iPod Software Updates\iPod1,1_2.0_5A347_Restore.ipsw
5. Held Shift while clicking Restore in iTunes
6. Selected Firmware 2.0 file (above)
7. Wait 10 minutes, restore and installation should complete
8. Connect to computer 1.
9. Sync all your media back on and enjoy app store!