I had a similar problem, it was because i was trying to upgrade to iphone firmware and not ipod touch firmware. so just makes sure it says iPod 1,1.1.1 firmware and not iPhone 1,1.1.1 firmware (thats if you downloaded of a webpage)
Also a had another problem where I downloaded the firmware from an untrusted site and it was corrupt, so download iPod 1.1.1 firmware from this site>>>
http://modmyi.com/forums/downloads.php?do=file&id=2027 download that, shift click on restore in itunes and find this file^^^ that you downloaded. Then you know the proccess from there... jailbreakme.com I see no reason why I wouldn't work... Hope that helped.