I stumbled across a pretty simple work around earlier today and it seems to work.
1. Install the latest version of Growl (1.1.2)
2. Follow the instructions on this page:
http://forums.cocoaforge.com/viewtopic.php?t=15587
3. In the Applications tab in the Growl preference pane, you'll see one called "New Mail Rule"
4. Click on it and select "Configure"
5. Then you'll see the "Play Sound" drop down box. Pick your favorite mail sound.
And that's all there is to it. Not only does this get Growl working with Leopard, but it also gives you your new mail sound back.