I've recently had this problem myself, but with different iPods. I was using a 3g 40 GB iPod and recently upgraded to a 60 GB iPod Photo. I'm using Windows98, but was able to format the firmware to the latest version using a computer with XP on display at CompUSA. At first, everything seemed okay, but, like Madcow, everything was quieter and all the songs played at their various native volumes.
The first initializing, I suppose I was multitasking too many things at once and the iPod database got corrupted with gibberish file lists. While that's only cosmetic, it's still a pain. "Rebuild database from iPod" is a command that has never worked for me. It takes forever, and when it's finally done, at least for me, MC locks up and performs an illegal operation, and this occurs every time I click on it and MC tries to read the database. I have to manually delete the iTunes files and then iniatialize again (or run Apple restore software at CompUSA again if I want to waste some time). The second initializing and upload, it turned out with a good database, but this is where I had the replay gain problem.
I don't know what causes all of this, but I just initialized again and transferred two songs I knew had significant volume differences and it seems to work. I just hope when I upload the other songs, everything'll be okay this time. I'm using 10.0.173.