Other posters on other threads seem to suggest that Windows formatted iPods can work on both Windows and Mac; my experience was yours, however, and I received that same message when I connected my iPod to my new MBP (the kind chap in the Apple shop had already transferred all of my files, installed Office for Mac, and most importantly, transferred iTunes for me.) I checked both iTunes and iPod today when I read your post and wracked my memory; my recollection is that it was very easy and pretty straightforward and involved the "restore" button; when that comes up as restore factory settings, and the factory settings have been restored, (which wipes the iPod by the way; you'll have to reinstall iTunes, and your music library, and may mislay your playlists along the way, but that does not take long) you type in Macintosh rather than Windows when it asks you how you wish to have it formatted. That's it. Cheers and good luck.