Try...
Go to Start -> Settings -> Control Panel -> Sounds and Audio Devices -> go to the "Sounds" tab -> scroll down to "New Mail Notification" -> and then change it.
Your route to "Sounds and Audio Devices" might be a little different if you stuck with the default XP Control Panel. I switched to the simpler Classic version.