Apple's 1.1.3 Touch upgrade must be available. If you go to Apples site and go to the Touch Page, there is a link to upgrade you older Touch for $19.95. It then launches the iTunes store and you can proceed from there. The 1.1.3 upgrade will cost you no matter what. So, it must be available now.
I assume the new Touchs already have it installed, therefore new upgrades for them MIGHT not cost anything. cough cough
EDIT: Plug in your Touch and hit update. It is available now. You can back out and tell it not to bother you until you want it.