Today I got a new ipod touch 16g. I downloaded the new itunes 8 as well
When i connected the ipod neither windows nor itunes recognized it. So i dfu'd it and put it in recovery mode so my itunes would recognize it. well, itunes recognized it and when i went to restore it i got an error message telling me that i dont have the latest software.....
That is very odd. So, you try to restore and it won't let you? That is very odd. That would sound like it's your iTunes not recognizing it (there is a chance it is the iPod, but it is unlikely). Reinstall iTunes and try it again. It should allow you to restore, but if it wont, download the 2.1 iPod firmware and shift (option, if on a Mac) + click and search for your firmware.
I would definitely try to take it back before you spend slot of time working on it. Did you try to jailbreak or just straight out of the box? I agree with jeckel though. ITunes' fault.