Please note that message is telling you to install the 'iPod Software Updater Application' you'll find on the cd-disc that came with the iPod, it is not telling you about to install-uninstall-update your actual version of iTunes. Of course the newer the iTunes version installed the better.
This is the icon of the iPod Software Updater application, maybe you have it inside the Utilites folder…
