Is the computer authorized for the iTunes accounts that purchased the apps?
Do you have Restrictions set that prohibit installing apps? (Settings>General>Restrictions)
Did you do the update on another computer?
You said you have a new computer. If you never synced to that computer before you have to do the following since an iPod can only sync to one computer:
- Transfer iTunes purchases by:
iTunes Store: Transferring purchases from your iOS device or iPod to a computer
- For other music you need a third-party program like one of those discussed here:
Copy music
- Connect the iPod to the computer and make a backup by right clicking on the iPod under Devices in iTunes and select Back Up.
- Restore the iPod from that backup
Note that the backup that iTunes makes does not include media like app and music.