Hi amigos:
Same happen to me as soon as the new release (1.1.3). Sounds weird but the only think you have to do is plug and unplug your iPod 3 0r 4 times.
I can assure you that after 4 or 5 tries everything will be ok.
Why is happening that?
Think Apple sold so many iPod (4,000,000) and we are trying to get it at the same time, so they cant handle to manage all of them. Maybe there is not as much slot as they need for everyone to download the new version. Because you cant download the new release your iPod don't get the new software while the old one is deleted.
Believe me, try to plug/unplug 4 or 5 times at the problem will be solve. Or much better, just next time don't try to upgrade as soon as the new release is on iTunes and wait 1 week