I've had the chance to use 3 different 3g nanos and it is beginning to look like they've got a conspiracy against me. I had the same problem with Win XP, now I'm using Windows 7 and the problem proceeds its existance.
Whenever I connect my iPod to my computer, iTunes says it has discovered an iPod in recovery mode and I need to reset it. Always. I've done some searching and surprisingly enough I didn't find a solution for this, even though I've had the same problem with each and every iPod 3g nano I've used in the past.