[jonnny]

Try deauthorizing, then re-authorizing your computer with the iTunes Music Store:

Disconnect your iPod first, then in iTunes:

Advanced -> Deauthorize Computer

then play one of your iTMS-purchased songs and enter your Apple ID and Password when prompted.

Reconnect your iPod, and update it.