Apple has released iPod Update 2004-04-28 which supports all models of iPod and iPod mini introduced before April 28, 2004. This update is required to take advantage of new features in iTunes 4.5 and the iTunes Music Store.
Changes for iPod without a Dock connector:
– Compatibility with iTunes 4.5 and the iTunes Music Store
– Improved playback performance
Changes for iPod with a Dock connector and iPod mini:
– Compatibility with iTunes 4.5 and the iTunes Music Store
– Improved playback performance
– Support for the Apple Lossless Encoder, to enable compressed music encoding at high quality
More info and download link here.