I may be wrong, but it sounds like you've got some music in your iTunes library that was purchased from the iTunes Music Store, but the computer that you're using to sync with your iPod isn't authorized to play those songs. I'd start with the example song in the error message you're getting. Make sure you can play it in iTunes.
Since an iPod can only sync with one computer, once you authorize the computer to play the song, every song purchased with that account will be able to load onto your iPod and the messages will go away. And your number of songs in your library and on your iPod should match again.
Doc