Did you do this with the Mail App closed? If the app is already open it won't take effect......close the app completely and then reopen and see if that makes a difference.
From the home screen do the four finger swipe up or double press the home button to reveal your multi task bar. These are all the apps that you have opened at one time. If you have updated to IOS7 - just swipe up on the image above the app icon to close it. If on an earlier OS - Long press the app until it jiggles and a red minus sign will appear above it. Press the minus sign, this will close the app, not delete it, now press the home button to return to your screen.
I close the Mail app, go to Settings, then to Sounds, then to New Mail, then to Alert Sounds, then to Classics, then to Sherwood Forest, but when receiving mail the alert is still Chord.